Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on hypergraphs without non-trivial intersecting subgraphs
85
0
0.0
(
0
)
Authors
Xizhi Liu
Ask ChatGPT about the research
No Arabic abstract
A hypergraph $mathcal{F}$ is non-trivial intersecting if every two edges in it have a nonempty intersection but no vertex is contained in all edges of $mathcal{F}$. Mubayi and Verstra{e}te showed that for every $k ge d+1 ge 3$ and $n ge (d+1)n/d$ every $k$-graph $mathcal{H}$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $binom{n-1}{k-1}$ edges. They conjectured that the same conclusion holds for all $d ge k ge 4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $m ge 4$ and sufficiently large $n$ the maximum size of a $3$-graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner systems. We give a construction with more edges showing that their conjecture is not true in general.
rate research
Read More
This exposition contains a short and streamlined proof of the recent result of Kwan, Letzter, Sudakov and Tran that every triangle-free graph with minimum degree $d$ contains an induced bipartite subgraph with average degree $Omega(ln d/lnln d)$.
Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Y. Peng and C. Zhao (2012) and extend a result of J. Talbot (2002). keywords{Cliques of hypergraphs and Colex ordering and Lagrangians of hypergraphs and Polynomial optimization}
For positive integers $n,r,k$ with $nge r$ and $kge2$, a set ${(x_1,y_1),(x_2,y_2),dots,(x_r,y_r)}$ is called a $k$-signed $r$-set on $[n]$ if $x_1,dots,x_r$ are distinct elements of $[n]$ and $y_1dots,y_rin[k]$. We say a $t$-intersecting family consisting of $k$-signed $r$-sets on $[n]$ is trivial if each member of this family contains a fixed $k$-signed $t$-set. In this paper, we determine the structure of large maximal non-trivial $t$-intersecting families. In particular, we characterize the non-trivial $t$-intersecting families with maximum size for $tge2$, extending a Hilton-Milner-type result for signed sets given by Borg.
A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran independently showed that for $ngeq 2k + csqrt{kln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $ngeq 2k+ 100ln k$. Our proof uses, among others, Sapozhenkos graph container lemma and the Das-Tran removal lemma.
Let $kge 3$ be an odd integer and let $n$ be a sufficiently large integer. We prove that the maximum number of edges in an $n$-vertex $k$-uniform hypergraph containing no $2$-regular subgraphs is $binom{n-1}{k-1} + lfloorfrac{n-1}{k} rfloor$, and the equality holds if and only if $H$ is a full $k$-star with center $v$ together with a maximal matching omitting $v$. This verifies a conjecture of Mubayi and Verstra{e}te.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
