Abstract. We study the extremal number for paths in [Formula: see text]-uniform hypergraphs where two consecutive edges of the path intersect alternately in sets of sizes [Formula: see text] and [Formula: see text] with [Formula: see text] and all other pairs of edges have empty intersection. Our main result, which is about hypergraphs that are blowups of trees, determines asymptotically the extremal number of these [Formula: see text]-paths that have an odd number of edges or that have an even number of edges and [Formula: see text]. This generalizes the Erdős–Gallai theorem for graphs, which is the case of [Formula: see text]. Our proof method involves a novel twist on Katona’s permutation method, where we partition the underlying hypergraph into two parts, one of which is very small. We also find the asymptotics of the extremal number for the [Formula: see text]-path of length 4 using the different [Formula: see text]-systems method.

We prove a minimum degree version of the Kruskal--Katona theorem for triple systems: given $d\ge 1/4$ and a triple system $\mathcal{F}$ on $n$ vertices with minimum degree $\delta(\mathcal{F})\ge d\binom n2$, we obtain asymptotically tight lower bounds for the size of its shadow. Equivalently, for $t\ge n/2-1$, we asymptotically determine the minimum size of a graph on $n$ vertices, in which every vertex is contained in at least $\binom t2$ triangles. This can be viewed as a variant of the Rademacher--Turán problem.

An $r$-uniform hypergraph is a tight $r$-tree if its edges can be ordered so that every edge $e$ contains a vertex $v$ that does not belong to any preceding edge and the set $e-v$ lies in some preceding edge. A conjecture of Kalai personal communication published in Frankl and Füredi, J. Combin. Theory Ser. A, 45 (1987), pp. 226--262, generalizing the Erdös--Sós conjecture for trees, asserts that if $T$ is a tight $r$-tree with $t$ edges and $G$ is an $n$-vertex $r$-uniform hypergraph containing no copy of $T$, then $G$ has at most $\frac{t-1}{r}\binom{n}{r-1}$ edges. A trunk $T'$ of a tight $r$-tree $T$ is a tight subtree such that every edge of $T-T'$ has $r-1$ vertices in some edge of $T'$ and a vertex outside $T'$. For $r\ge 3$, the only nontrivial family of tight $r$-trees for which this conjecture has been proved is the family of $r$-trees with trunk size one in J. Combin. Theory Ser. A, 45 (1987), pp. 226--262. Our main result is an asymptotic version of Kalai's conjecture for all tight trees $T$ of bounded trunk size. This follows from our upper bound on the size of a $T$-free $r$-uniform hypergraph $G$ in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight $r$-trees with at most four edges. In particular, for 3-uniform hypergraphs, our result on the tight path of length $4$ implies the intersection shadow theorem of Katona Acta Math. Acad. Sci. Hungar., 15 (1964), pp. 329--337.

Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v \mapsto A_v$ to the vertices $v\in V$ such that $A_u$ and $A_v$ are disjoint if and only if $uv\in E$. The smallest such $k$ is called the Kneser rank of $G$ and denoted by $f_{\rm Kneser}(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0< p< 1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$, such that $G\in {\mathcal G}(n, p)$ satisfies with high probability $ c_1 n/(\log n)< f_{\rm Kneser}(G) < c_2 n/(\log n). $ We apply this for other graph representations defined by Boros, Gurvich, and Meshulam. A $k$-min-difference representation of a graph $G$ is an assignment of a set $A_i$ to each vertex $i\in V(G)$ such that $ ij\in E(G) \,\, \Leftrightarrow \, \, \min \{|A_i\setminus A_j|,|A_j\setminus A_i| \}\geq k. $ The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{\min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{\min}(G)\geq k$. We prove that there are constants $c''_1, c''_2>0$ such that $c''_1 n/(\log n)< f_{\min}(G) < c''_2n/(\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.

For a property $\Gamma$ and a family of sets ${\mathcal F}$, let $f({\mathcal F},\Gamma)$ be the size of the largest subfamily of ${\mathcal F}$ having property $\Gamma$. For a positive integer m, let $f(m,\Gamma)$ be the minimum of $f({\mathcal F},\Gamma)$ over all families of size m. A family ${\mathcal F}$ is said to be $B_d$-free if it has no subfamily ${\mathcal F}'=\{F_I: I \subseteq [d]\}$ of $2^d$ distinct sets such that for every $I,J \subseteq [d]$, both $F_I \cup F_J=F_{I \cup J}$ and $F_I \cap F_J = F_{I \cap J}$ hold. A family ${\mathcal F}$ is a-union-free if $F_1\cup \dots \cup F_a \neq F_{a+1}$ whenever $F_1,\dots,F_{a+1}$ are distinct sets in ${\mathcal F}$. We verify a conjecture of Erdős and Shelah that $f(m, B_2\text{\rm -free})=\Theta(m^{2/3})$. We also obtain lower and upper bounds for $f(m, B_d\text{\rm -free})$ and $f(m,a\text{\rm -union free})$.

We have found a general extension of the celebrated Sauer, Perles and Shelah, Vapnik and Chervonenkis result from 0-1 sequences to k-ary codes still giving a polynomial bound. Let $\mathcal{C}\subseteq \{ 0,1,\dots, k-1 \}^n$ be a k-ary code of length n. For a subset of coordinates $S\subset \{1,2,\ldots ,n\}$, the projection of $\mathcal{C}$ to S is denoted by $\mathcal{C}\vert_S$. We say that $\mathcal{C}$ $(i,j)$-shatters S if $\mathcal{C}\vert_S$ contains all the $2^{|S|}$ distinct vectors (codewords) with coordinates i and j. Suppose that $\mathcal{C}$ does not $(i,j)$-shatter any coordinate set of size $s_{i,j}\geq 1$ for every $0\leq i< j\leq k-1$, and let $p=\sum (s_{i,j}-1)$. Using a natural induction we prove that $|{\mathcal C}|\leq O(n^p) $ as $n\to \infty$. We give a construction showing that this exponent is the best possible. Several open problems are mentioned.

A set $\mathcal{F}$ of ordered k-tuples of distinct elements of an n-set is pairwise reverse free if it does not contain two ordered k-tuples with the same pair of elements in the same pair of coordinates in reverse order. Let $F(n,k)$ be the maximum size of a pairwise reverse-free set. In this paper we focus on the case of 3-tuples and prove $\lim F(n,3)/\binom{n}{3}=5/4$, more exactly, $\frac{5}{24}n^3-\frac{1}{2}n^2-O(n\log n)

This is a paper about the beauty of the permutation method. New and shorter proofs are given for the theorem [P. L. Erdos and G. O. H. Katona, J. Combin. Theory. Ser. A, 43 (1986), pp. 58--69; S. Shahriari, Discrete Math., 162 (1996), pp. 229--238] determining all extremal two-part Sperner families and for the uniqueness of k-Sperner families of maximum size [P. Erdos, Bull. Amer. Math. Soc., 51 (1945), pp. 898--902].

A family of n-dimensional unit norm vectors is an Euclidean superimposed code if the sums of any two distinct at most m-tuples of vectors are separated by a certain minimum Euclidean distance d. Ericson and Gyorfi (1988) proved that the rate of such a code is between (log m)/4m and (log m)/m for m large enough. In this paper-improving the above long-standing best upper bound for the rate-it is shown that the rate is always at most (log m)/2m, i.e., the size of a possible superimposed code is at most the root of the size given by Ericson et al. We also generalize these codes to other normed vector spaces.

Let $f( n )$ be the minimum over all convex planar n-gons of the number of different midpoints of the $\begin{pmatrix} n \\ 2 \end{pmatrix}$ line segments, or diagonals, between distinct vertices. It is proved that $f( n )$ is between approximately $0.8 \begin{pmatrix} n \\ 2 \end{pmatrix} $ and $0.9 \begin{pmatrix} n \\ 2 \\ \end{pmatrix} $. The upper bound uses the fact that the number of multiple midpoints, shared by two or more diagonals, can be as great as about $\begin{pmatrix} n \\ 2 \end{pmatrix}/10$. Cases for which the number of midpoints is at least $\lceil n( n - 2 )/2 \rceil + 1$, the number for a regular n-gon when n is even, are noted.

A set of points is independent if there are no three on a line. It is proved that $\Omega ( \sqrt {n\log n} ) < \alpha ( n ) < o( n )$, where $\alpha ( n )$ denotes the maximum $\alpha $ such that every planar set of n points with no four on a line contains an independent subset of size $\alpha $.

Let S ⊂ R3 be an n-set in general position. A plane containing three of the points is called a halving plane if it dissects S into two parts of equal cardinality. It is proved that the number of halving planes is at most Ο(n2.998).

Given a graph G and $d \in \mathbb{Z}^+$, the pair labelling number, $r(G,d)$, is defined to be the minimum n such that each vertex in G can be assigned a pair of numbers from $\{ 1, \cdots ,n\} $ in such a way that any two numbers used at adjacent vertices differ by at least d. A question of Roberts’ is answered by determining all possible values of $r(G,d)$ given the chromatic number of G. The answer follows by determining the chromatic number of the graph that has pairs of integers as vertices and edges joining pairs that are distance at least d apart. For general $t \in \mathbb{Z}^+$, the analogous questions for t-sets instead of pairs are considered. A solution for general t is conjectured which, for $d = 1$, reduces to Lovász's theorem on Kneser graphs.

The fractional covering number$\tau^*$ of a hypergraph $H = ( V, E )$ is defined to be the minimum possible value of $\sum_{x \in V} t( x )$ where t ranges over all functions $t : V \to \mathbb{R}$ which satisfy $\sum_{x \in e} t ( x ) \geqq 1$ for all edges $e \in E$. In the case of ordinary graphs G, it is known that $2\tau^* ( G )$ is always an integer. By contrast, it is shown (among other things) that for any rational $p/q\geqq 1$, there is a 3-uniform hypergraph H with $\tau^* ( H ) = p/q$.

Article Computing the volume is difficult Share on Authors: Z Furedi View Profile , I Barany View Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 442–447https://doi.org/10.1145/12130.12176Online:01 November 1986Publication History 15citation351DownloadsMetricsTotal Citations15Total Downloads351Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access