Search

Let f^{(r)}(n;s,k) be the maximum number of edges of an r-uniform hypergraph on n vertices not containing a subgraph with k edges and at most s vertices. In 1973, Brown, Erdős, and Sós conjectured that the limit \begin{equation*} \lim _{n\to \infty } n^{-2} f^{(3)}(n;k+2,k) \end{equation*} exists for all k and confirmed it for k=2. Recently, Glock showed this for k=3. We settle the next open case, k=4, by showing that f^{(3)}(n;6,4)=\left (\frac {7}{36}+o(1)\right)n^2 as n\to \infty. More generally, for all k\in \{3,4\}, r\ge 3 and t\in [2,r-1], we compute the value of the limit \lim _{n\to \infty } n^{-t}f^{(r)}(n;k(r-t)+t,k), which settles a problem of Shangguan and Tamo. [ABSTRACT FROM AUTHOR]

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]

The MaxCut problem asks for the size mc(G)${\rm mc}(G)$ of a largest cut in a graph G$G$. It is well known that mc(G)⩾m/2${\rm mc}(G)\geqslant m/2$ for any m$m$‐edge graph G$G$, and the difference mc(G)−m/2${\rm mc}(G)-m/2$ is called the surplus of G$G$. The study of the surplus of H$H$‐free graphs was initiated by Erdős and Lovász in the 70s, who, in particular, asked what happens for triangle‐free graphs. This was famously resolved by Alon, who showed that in the triangle‐free case the surplus is Ω(m4/5)$\Omega (m^{4/5})$, and found constructions matching this bound. We prove several new results in this area. (i)Confirming a conjecture of Alon, Krivelevich and Sudakov, we show that for every fixed odd r⩾3$r\geqslant 3$, any Cr$C_r$‐free graph with m$m$ edges has surplus Ωr(mr+1r+2)$\Omega _r(m^{\frac{r+1}{r+2}})$. This is tight, as is shown by a construction of pseudo‐random Cr$C_r$‐free graphs due to Alon and Kahale. It improves previous results of several researchers, and complements a result of Alon, Krivelevich and Sudakov which is the same bound when r$r$ is even.(ii)Generalising the result of Alon, we allow the graph to have triangles, and show that if the number of triangles is a bit less than in a random graph with the same density, then the graph has large surplus. For regular graphs, our bounds on the surplus are sharp.(iii)We prove that an n$n$‐vertex graph with few copies of Kr$K_r$ and average degree d$d$ has surplus Ωr(dr−1/nr−3)$\Omega _r(d^{r-1}/n^{r-3})$, which is tight when d$d$ is close to n$n$ provided that a conjectured dense pseudo‐random Kr$K_r$‐free graph exists. This result is used to improve the best known lower bound (as a function of m$m$) on the surplus of Kr$K_r$‐free graphs.Our proofs combine techniques from semi‐definite programming, probabilistic reasoning, as well as combinatorial and spectral arguments. [ABSTRACT FROM AUTHOR]

In 1994, Erdős, Gyárfás and Łuczak posed the following problem: given disjoint vertex sets V 1 , ... , V n of size k , with exactly one edge between any pair V i , V j , how large can n be such that there will always be an independent transversal? They showed that the maximal n is at most (1 + o (1)) k 2 , by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a 2 e -factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if n ≤ (1 − o (1)) k 2 , there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are 'locally sparse', meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global maximum degree condition for the existence of an independent transversal. We show that this can be relaxed to an average degree condition. We can also use our new theorem to establish tight bounds for a more general version of the Erdős–Gyárfás–Łuczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turán numbers of complete bipartite graphs, which might be of independent interest. [ABSTRACT FROM AUTHOR]

For a hypergraph H$H$, define its intersection spectrum I(H)$I(H)$ as the set of all intersection sizes |E∩F|$|E\cap F|$ of distinct edges E,F∈E(H)$E,F\in E(H)$. In their seminal paper from 1973 which introduced the local lemma, Erdős and Lovász asked: how large must the intersection spectrum of a k$k$‐uniform 3‐chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with k$k$. Despite the problem being reiterated several times over the years by Erdős and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdős–Lovász conjecture in a strong form by showing that there are at least k1/2−o(1)$k^{1/2-o(1)}$ intersection sizes. Our proof consists of a delicate interplay between Ramsey‐type arguments and a density increment approach. [ABSTRACT FROM AUTHOR]

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of K2n+1 into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large n. [ABSTRACT FROM AUTHOR]

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K 2 n , there exists a decomposition of K 2 n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi–Hollingsworth (from 1996) and Constantine (from 2002) for large graphs. [ABSTRACT FROM AUTHOR]

We study the F -decomposition threshold δ F for a given graph F. Here an F -decomposition of a graph G is a collection of edge-disjoint copies of F in G which together cover every edge of G. (Such an F -decomposition can only exist if G is F -divisible, i.e. if e (F) | e (G) and each vertex degree of G can be expressed as a linear combination of the vertex degrees of F.) The F -decomposition threshold δ F is the smallest value ensuring that an F -divisible graph G on n vertices with δ (G) ≥ (δ F + o (1)) n has an F -decomposition. Our main results imply the following for a given graph F , where δ F ⁎ is the fractional version of δ F and χ : = χ (F) : (i) δ F ≤ max ⁡ { δ F ⁎ , 1 − 1 / (χ + 1) } ; (ii) if χ ≥ 5 , then δ F ∈ { δ F ⁎ , 1 − 1 / χ , 1 − 1 / (χ + 1) } ; (iii) we determine δ F if F is bipartite. In particular, (i) implies that δ K r = δ K r ⁎. Our proof involves further developments of the recent 'iterative' absorbing approach. [ABSTRACT FROM AUTHOR]

We show that the maximum number of triples on n points, if no three triples span at most five points, is (1±o(1))n2/5. More generally, let f(r)(n;k,s) be the maximum number of edges in an r‐uniform hypergraph on n vertices not containing a subgraph with k vertices and s edges. In 1973, Brown, Erdős and Sós conjectured that the limit limn→∞n−2f(3)(n;k,k−2) exists for all k. They proved this for k=4, where the limit is 1/6 and the extremal examples are Steiner triple systems. We prove the conjecture for k=5 and show that the limit is 1/5. The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate H‐decompositions of Kn for a suitably defined graph H. [ABSTRACT FROM AUTHOR]

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let 0 < p < 1 be constant and let G ∼ G n , p . Let odd ( G ) be the number of odd degree vertices in G . Then a.a.s. the following hold: (i) G can be decomposed into ⌊ Δ ( G ) / 2 ⌋ cycles and a matching of size odd ( G ) / 2 . (ii) G can be decomposed into max ⁡ { odd ( G ) / 2 , ⌈ Δ ( G ) / 2 ⌉ } paths. (iii) G can be decomposed into ⌈ Δ ( G ) / 2 ⌉ linear forests. Each of these bounds is best possible. We actually derive (i)–(iii) from ‘quasirandom’ versions of our results. In that context, we also determine the edge chromatic number of a given dense quasirandom graph of even order. For all these results, our main tool is a result on Hamilton decompositions of robust expanders by Kühn and Osthus. [ABSTRACT FROM AUTHOR]

Our motivation is the question how similar thef-colouring problem is to the classic edge-colouring problem, particularly with regard to graph parameters. In 2010, Zhanget al.[On the fractional f-chromatic index of a graph, Int. J. Comput. Math. 87 (2010), pp. 3359–3369] gave a new description of thef-matching polytope and thereby derived a formula for the fractionalf-chromatic index stating that the fractionalf-chromatic index is equal to the maximum of the fractional maximumf-degree and the fractionalf-density. Unfortunately, this formula is incorrect. We present counterexamples for both the description of thef-matching polytope and the formula for the fractionalf-chromatic index. Finally, we prove a short lemma concerning the generalization of Goldberg's conjecture. [ABSTRACT FROM PUBLISHER]

A new semi-physical memoryless computationally effective behavioral model (BM) capable of predicting amplitude-modulation-to-amplitude-modulation (AM–AM) and amplitude-modulation-to-phase-modulation (AM–PM) distortions is proposed. In recent years, AM–AM and AM–PM distortions have been separately studied in literature. Here, we investigate the correlation between AM–AM and AM–PM distortions first. Based on the observed correlation, a novel AM–PM model is derived from the well-known Rapp AM–AM model. On the basis of the close relationship between the AM–AM and AM–PM model, a highly accurate and computationally effective large-signal BM is obtained. The newly developed model addresses the current needs of the mobile industry that requires BMs of the power amplifier (PA), which can be interpreted by the designers. In addition, the models must be computationally effective due to the limited computation power in mobile handset. Therefore, only memoryless BMs can be taken into account and larger errors are accepted for the sake of computational effectiveness. In this paper, it is shown that the newly introduced model achieves excellent results, when it is applied to actual industrial applications of two GaAs-based class-AB PAs in 65-nm technology and one CMOS-based class AB PA in 28-nm technology, which are designed for mobile communications. [ABSTRACT FROM PUBLISHER]