Minimal paths and cycles in set systems

DOI10.1016/J.EJC.2006.07.001MaRDI QIDQ2372429zbMATH OpenOpenAlexFDO

Authors Dhruv Mubayi, J. Verstraëte

Publication date 27 July 2007

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2006.07.001

zbMATH Keywords

Erdős-Ko-Rado theoremminimal cycleminimal path

Mathematics Subject Classification ID

Paths and cycles (05C38) Extremal set theory (05D05)

Review text

A family of sets \(A_0,\dots,A_{k-1}\) form a minimal \(k\)-cycle if \(A_i\cap A_j \neq \emptyset\) if and only if \((i=j\) or these two are consecutive modulo \(k).\) Denote \(f_r(n,k)\) the maximum size of a family of \(r\)-sets of an \(n\)-element underlying set, not containing minimal \(k\)-cycle. The paper determines new lower and upper bounds for this value. The proofs are based on classical extremal set theoretical results of Paul Erdős and others.

Recommendations

• Hypergraph Turán numbers of linear cycles
• Minimal unavoidable sets of cycles in plane graphs
• A note on a series of families constructed over the cyclic graph
• scientific article; zbMATH DE number 4085657
• Turán problems and shadows. I: Paths and cycles

Cites work

• A hypergraph extension of the bipartite Turán problem
• A lower bound for families of Natarajan dimension d
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• Hypergraphs in which all disjoint pairs have distinct unions
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Large cycles in graphs
• On chromatic‐choosable graphs
• On coloring graphs to maximize the proportion of multicolored k-edges
• On hypergraphs of girth five
• On maximal paths and circuits of graphs
• On the choice number of claw-free perfect graphs
• Proof of a conjecture of Erdős on triangles in set-systems
• Sufficient Conditions for Circuits in Graphs^†

Cited in

(19)

• The maximum size of hypergraphs without generalized 4-cycles
• Linear Turán numbers of acyclic triple systems
• On extremal hypergraphs for forests of tight paths
• Hypergraph Turán numbers of linear cycles
• Linear trees in uniform hypergraphs
• Complete characterization of bicyclic minimal configurations
• Alternating paths and cycles of minimum length
• Simplex stability
• Exact solution of the hypergraph Turán problem for k-uniform linear paths
• Minimal unavoidable sets of cycles in plane graphs
• Turán problems and shadows. I: Paths and cycles
• Anti-Ramsey numbers of paths and cycles in hypergraphs
• Set systems without a simplex or a cluster
• Turán and Ramsey numbers for 3‐uniform minimal paths of length 4
• The spectral radius of the hypergraphs without the expansion of P₃ or Berge-P_k
• Some exact and asymptotic results for hypergraph Turán problems in _2-norm
• Bounds on linear Turán number for trees
• Hypergraph extensions of the Erdős-Gallai theorem
• Note on set systems without a strong simplex

This page was built for publication: Minimal paths and cycles in set systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372429)