Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew bounds for a hypergraph Bipartite Turan problem
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $t$ be an integer such that $tgeq 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples ${a,x_i,y_i}$, ${b,x_i,y_i}$ for $1 le i le t$, where the elements $a, b, x_1, x_2, ldots, x_t,$ $y_1, y_2, ldots, y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstraete, where the special case $t=2$ was a problem of ErdH{o}s that was studied by various authors. Mubayi and Verstraete proved that $ex(n,K_{2,t}^{(3)})<t^4binom{n}{2}$ and that for infinitely many $n$, $ex(n,K_{2,t}^{(3)})geq frac{2t-1}{3} binom{n}{2}$. These bounds together with a standard argument show that $g(t):=lim_{nto infty} ex(n,K_{2,t}^{(3)})/binom{n}{2}$ exists and that [frac{2t-1}{3}leq g(t)leq t^4.] Addressing the question of Mubayi and Verstraete on the growth rate of $g(t)$, we prove that as $t to infty$, [g(t) = Theta(t^{1+o(1)}).]
rate research
Read More
Given $r$-uniform hypergraphs $G$ and $H$ the Turan number $rm ex(G, H)$ is the maximum number of edges in an $H$-free subgraph of $G$. We study the typical value of $rm ex(G, H)$ when $G=G_{n,p}^{(r)}$, the ErdH{o}s-Renyi random $r$-uniform hypergraph, and $H=C_{2ell}^{(r)}$, the $r$-uniform linear cycle of length $2ell$. The case of graphs ($r=2$) is a longstanding open problem that has been investigated by many researchers. We determine $rm ex(G_{n,p}^{(r)}, C_{2ell}^{(r)})$ up to polylogarithmic factors for all but a small interval of values of $p=p(n)$ whose length decreases as $ell$ grows. Our main technical contribution is a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan. The novelty is that the supersaturation result depends on the codegree of some pairs of vertices in the underlying hypergraph. This approach could be used to prove similar results for other hypergraphs $H$.
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
Classical questions in extremal graph theory concern the asymptotics of $operatorname{ex}(G, mathcal{H})$ where $mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a `standard increasing sequence of host graphs $(G_1, G_2, dots)$, most often $K_n$ or $K_{n,n}$. Inverting the question, we can instead ask how large $e(G)$ can be with respect to $operatorname{ex}(G,mathcal{H})$. We show that the standard sequences indeed maximize $e(G)$ for some choices of $mathcal{H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.
The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $mathcal{G}$ and $mathcal{H}$, decide whether $mathcal{H}$ consists precisely of all minimal transversals of $mathcal{G}$ (in which case we say that $mathcal{G}$ is the dual of $mathcal{H}$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $mathrm{GC}(log^2 n,mathrm{PTIME})$, where $mathrm{GC}(f(n),mathcal{C})$ denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $mathcal{C}$. It was conjectured that non-DUAL is in $mathrm{GC}(log^2 n,mathrm{LOGSPACE})$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $mathrm{GC}(log^2 n,mathrm{TC}^0)$ which is a subclass of $mathrm{GC}(log^2 n,mathrm{LOGSPACE})$. We here refer to the logtime-uniform version of $mathrm{TC}^0$, which corresponds to $mathrm{FO(COUNT)}$, i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for non-DUAL that requires to guess $O(log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in $mathrm{FO(COUNT)}$. From this result, by the well known inclusion $mathrm{TC}^0subseteqmathrm{LOGSPACE}$, it follows that DUAL belongs also to $mathrm{DSPACE}[log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $mathcal{G}$ and $mathcal{H}$, computes in quadratic logspace a transversal of $mathcal{G}$ missing in $mathcal{H}$.
Let the bipartite Turan number $ex(m,n,H)$ of a graph $H$ be the maximum number of edges in an $H$-free bipartite graph with two parts of sizes $m$ and $n$, respectively. In this paper, we prove that $ex(m,n,C_{2t})=(t-1)n+m-t+1$ for any positive integers $m,n,t$ with $ngeq mgeq tgeq frac{m}{2}+1$. This confirms the rest of a conjecture of Gy{o}ri cite{G97} (in a stronger form), and improves the upper bound of $ex(m,n,C_{2t})$ obtained by Jiang and Ma cite{JM18} for this range. We also prove a tight edge condition for consecutive even cycles in bipartite graphs, which settles a conjecture in cite{A09}. As a main tool, for a longest cycle $C$ in a bipartite graph, we obtain an estimate on the upper bound of the number of edges which are incident to at most one vertex in $C$. Our two results generalize or sharpen a classical theorem due to Jackson cite{J85} in different ways.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
