Set Systems, Designs and Hypergraphs

../

E0020/: Asks whether the number of n-element sets needed to force a k-sunflower grows only exponentially in n, with a base depending on k.

E0021/: Asks whether the smallest intersecting family of n-element sets in which every set of size at most n minus 1 misses a member has size linear in n.

E0083/: Bounds how large a family of half-size subsets of a set of 4n elements can be when every two members share at least two elements.

E0207/: Asks whether, for every g at least 2, large Steiner triple systems exist in which any j edges span at least j plus 3 vertices for j up to g.

E0231/: Asks whether every string of length 2^k over k letters contains two adjacent blocks that are permutations of each other; the site prints 2^k - 1, Erdős's misprint, and Keränen's word on four letters disproves it.

E0447/: The largest family of subsets of one through n in which no set is the union of two other distinct members of the family.

E0497/: Determines the number of antichains of subsets of an n-element set, that is, families in which no member contains another.

E0499/: Asks whether every n by n doubly stochastic matrix has a permutation along which the product of entries is at least n to the power minus n.

E0624/: Asks to prove that H(n) minus the base-two logarithm of n tends to infinity, where H(n) is the least size such that some map from the subsets of an n-element set X to X sends the subsets of each set that large onto X.

E0643/: Estimates how many edges force a t-uniform hypergraph on n vertices to have four edges with A union B equal to C union D and A, B and C, D disjoint.

E0644/: Bounds the size of a set meeting all k-element sets of a family in which every r of them share a piercing pair, asking if it is a constant times k.

E0664/: Concerns families of subsets of the first n integers, each of size above a constant times the square root of n, with any two sharing at most one element.

E0665/: Concerns pairwise balanced designs on the first n integers, families of sets in which every pair of distinct elements lies in exactly one set.

E0701/: Asks whether a family of sets closed under subsets always has an element contained in as many members as the largest intersecting subfamily has sets.

E0702/: Asks whether, for k at least 4 and n large in terms of k, more k-subsets of the first n integers than those through a fixed pair force two meeting in one point; Frankl proved it, while the site's wording, with no range, fails.

E0703/: The largest family of subsets of the first n integers in which no two members intersect in exactly r elements.

E0716/: Asks whether the largest 3-uniform hypergraph on n vertices containing no three edges spanning six vertices has o(n squared) edges, fewer than any fixed fraction of n squared for large n.

E0719/: Asks whether every r-uniform hypergraph on n vertices is a union of at most ex_r(n; K_{r+1}^r) edges and (r+1)-cliques, no two sharing an edge; the Erdős–Sauer conjecture, known for r = 2.

E0722/: Asks whether a Steiner system on n points with blocks of size k covering every r-set once exists for large n whenever the divisibility conditions hold.

E0723/: Asks whether the order of a finite projective plane must always be a power of a prime.

E0724/: Asks whether the largest number of mutually orthogonal Latin squares of order n grows at least as fast as a constant times the square root of n.

E0725/: Asks for an asymptotic formula for the number of Latin rectangles with k rows and n columns.

E0732/: Asks whether at least exp(c n^(1/2) log n) increasing sequences of block sizes arise from a design on n points in which every pair of points lies in exactly one block.

E0734/: Asks for a non-trivial pairwise balanced design on n points in which each block size is used at most about the square root of n times.

E0747/: Determines how many edges a random three-uniform hypergraph on three n vertices needs so that it almost surely has n disjoint edges.

E0775/: Asks whether a three-uniform hypergraph on n vertices can have at least n minus O(1) different sizes of maximal complete subgraphs.

E0776/: Asks how large n must be, in terms of r, for an antichain of subsets of one to n in which every occurring size is used at least r times to reach n minus 3 distinct sizes; three claims are pending, none accepted.

E0834/: Asks whether there is a three-critical three-uniform hypergraph in which every vertex has degree at least seven.

E0835/: Asks whether some k above two lets the k-element subsets of the integers up to two k get k plus one colors so every k plus one of them sees all colors.

E0837/: Asks for the set A_3 of densities alpha such that 3-uniform hypergraphs of limiting density above alpha must have growing subgraphs of density above some fixed beta > alpha, while limiting density at least alpha need not.

E0857/: Estimates the least number of subsets of the integers up to n that forces a sunflower of size k, meaning k of them with equal pairwise intersections.

E0901/: Estimates the least number of edges in an n-uniform hypergraph that cannot be colored with two colors but can with three.

E0903/: Concerns block designs on p squared plus p plus one points, for a prime power p, in which every pair of points lies in exactly one block.

E1020/: Asks whether, for r at least 3 and n at least rk, the most edges in an r-uniform hypergraph on n vertices with no k pairwise disjoint edges is the larger of the clique count and the star count.

E1022/: Asks whether sets of size at least t, few of which lie inside any given set relative to its size, can always be two-colored with no monochromatic member.

E1023/: Asks whether the largest family of subsets of the first n integers with no member a union of others is a constant times two to the n over the square root of n.

E1024/: Estimates the largest independent set guaranteed in a three-uniform hypergraph on n vertices in which any two edges share at most one vertex.

E1025/: Independent sets for a function assigning to each pair from the first n integers a third value, meaning sets closed away from the values of their own pairs.

E1026/: Determines the largest possible sum of a monotonic subsequence of a sequence of n distinct real numbers.

E1027/: Concerns the union of a family of at most a constant times two to the n many sets each of size n, for large n.

E1075/: Concerns a constant larger than r to the power minus r, for each r at least three, in a property of r-uniform hypergraphs on many vertices.

E1076/: Asks whether, for k at least five, the most edges of a 3-uniform hypergraph on n vertices with no j vertices spanning j minus two edges for any j from four to k is asymptotic to n squared over six; false for the single family as printed.

E1159/: Asks whether there is a constant greater than one for which a stated combinatorial property holds.

E1178/: Determines the least number of vertices d such that forbidding all r-uniform hypergraphs with d vertices and e edges forces subquadratically many edges.

---

Finite set systems and hypergraphs: sunflowers and delta-systems, intersecting and union-free families, antichains, property B, block designs, Latin squares and finite projective planes, together with the general combinatorics problems the site tags no more finely.

Site tags routed here: combinatorics, graph theory, hypergraphs, intersecting family.