Search

We give a complete description of the set of triples (α,β,γ) of real numbers with the following property. There exists a constant K such that αn3+βn2+γn1−K is a lower bound for the matching number ν(G) of every connected subcubic graph G, where ni denotes the number of vertices of degree i for each i.

One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose G is a multigraph with maximum degree Δ , such that no vertex subset S of odd size at most Δ induces more than ( Δ + 1 ) ( | S | - 1 ) / 2 edges. Then G has an edge coloring with Δ + 1 colors. Here we prove a weakened version of this statement.

In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph $G$, the chromatic index $\chi'(G)$ satisfies $\chi'(G)\leq \max \{\Delta(G)+1, \lceil\rho(G)\rceil\}$, where $\rho(G)=\max \{\frac {e(G[S])}{\lfloor |S|/2\rfloor} \mid S\subseteq V \}$. We show that their conjecture (in a stronger form) is true for random multigraphs. Let $M(n,m)$ be the probability space consisting of all loopless multigraphs with $n$ vertices and $m$ edges, in which $m$ pairs from $[n]$ are chosen independently at random with repetitions. Our result states that, for a given $m:=m(n)$, $M\sim M(n,m)$ typically satisfies $\chi'(G)=\max\{\Delta(G),\lceil\rho(G)\rceil\}$. In particular, we show that if $n$ is even and $m:=m(n)$, then $\chi'(M)=\Delta(M)$ for a typical $M\sim M(n,m)$. Furthermore, for a fixed $\varepsilon>0$, if $n$ is odd, then a typical $M\sim M(n,m)$ has $\chi'(M)=\Delta(M)$ for $m\leq (1-\varepsilon)n^3\log n$, and $\chi'(M)=\lceil\rho(M)\rceil$ for $m\geq (1+\varepsilon)n^3\log n$., Comment: 26 pages

We give an efficient algorithm that, given a graph $G$ and a partition $V_1,\ldots,V_m$ of its vertex set, finds either an independent transversal (an independent set $\{v_1,\ldots,v_m\}$ in $G$ such that $v_i\in V_i$ for each $i$), or a subset $\mathcal B$ of vertex classes such that the subgraph of $G$ induced by $\bigcup\mathcal B$ has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been applied to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here., Comment: This new version fixes a few typos and adds a brief overview of the analysis to Section 5. There is also further discussion of future work in Section 8

We give a construction of $r$-partite $r$-uniform intersecting hypergraphs with cover number at least $r-4$ for all but finitely many $r$. This answers a question of Abu-Khazneh, Barát, Pokrovskiy and Szabó, and shows that a long-standing unsolved conjecture due to Ryser is close to being best possible for every value of $r$.

It follows from known results that every regular tripartite hypergraph of positive degree, with $n$ vertices in each class, has matching number at least $n/2$. This bound is best possible, and the extremal configuration is unique. Here we prove a stability version of this statement, establishing that every regular tripartite hypergraph with matching number at most $(1 + \varepsilon)n/2$ is close in structure to the extremal configuration, where "closeness" is measured by an explicit function of $\varepsilon$. We also answer a question of Aharoni, Kotlar and Ziv about matchings in hypergraphs with a more general degree condition.

Motivated by an old problem known as Ryser's Conjecture, we prove that for $r=4$ and $r=5$, there exists $\epsilon>0$ such that every $r$-partite $r$-uniform hypergraph $\cal H$ has a cover of size at most $(r-\epsilon)\nu(\cal H)$, where $\nu(\cal H)$ denotes the size of a largest matching in $\cal H$.

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let fb(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then for some absolute constant B, thus establishing fb(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that We conjecture that f2(n) = n1 + o(1) as n → ∞.

Transversals in r-partite graphs with various properties are known to have many applications in graph theory and theoretical computer science. We investigate f-bounded transversal s (or f-BT), that is, transversals whose connected components have order at most f. In some sense we search for the sparsest f-BT-free graphs. We obtain estimates on the smallest maximum degree that 3-partite and 4-partite graphs without 2-BT can have and provide a greatly simplified proof of the best known general lower bound on the smallest maximum degree in f-BT-free graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory, © 2012 Wiley Periodicals, Inc. (Contract grant sponsors: JSPS Global COE program “Computationism as a Foundation for the Sciences” (to R. B.); NSERC (to P. H.))

A graph of order n is prime if one can bijectively label its vertices with integers 1, . . . , n so that any two adjacent vertices get coprime labels. We prove that all bipartite d-degenerate graphs with separators of size at most n1−Od(1/ ln lnn) are prime. It immediately follows that all large trees are prime, confirming an old conjecture of Entringer and Tout from around 1980. Also, our method allows us to determine the smallest size of a non-prime connected order-n graph for all large n, proving a conjecture of Rao [R. C. Bose Centenary Symposium on Discrete Math. and Applications, Kolkata, 2002] in this range.

Extending the Szemeredi Regularity Lemma for graphs, P. Frank and Rodl [2002] stablished a 3-graph Regularity Lemma guaranteeing that all large triple systems admit partitions of their edge sets into constantly many classes where most classes consist of regularly distributed edges. Many applications of this lemma require a companion Counting Lemma [Nagle and Rodl, 2003] allowing one to estimate the number of copies of K/sub k//sup 3/ in a "dense and regular" environment created by the 3-graph Regularity Lemma. Combined applications of these lemmas are known as the 3-graph Regularity Method. In this paper, we provide an algorithmic version of the 3-graph Regularity Lemma which, as we show, is compatible with a Counting Lemma. We also discuss some applications. For general k-uniform hypergraphs, Regularity and Counting Lemmas were recently established by Gowers [2005] and by Nagle et al., [2005]. We believe the arguments here provide a basis toward a general algorithmic hypergraph regularity method.

We give a self-contained elementary approach to a body of combinatorial results that were previously proved using topology. One example is the following hypergraph version of Hall’s Theorem, due to Aharoni and Haxell from 2000. Let \(\mathcal{H}\) be an r-uniform hypergraph with a vertex partition (A, X), in which every edge has exactly one vertex in A. Suppose that for every subset \(S \subseteq A\), the neighbourhood hypergraph \(\Gamma _{\mathcal{H}}(S)\) of S has a matching of size (r − 1)( | S | − 1) + 1. Then \(\mathcal{H}\) has a matching of size | A | .

Let Cn denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v1,…,vn and edges v1v2v3, v3v4v5, v5v6v7,…,vn-1vnv1. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of Cn, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.

Let $G$ be a finite graph with maximum degree at most $d$. Then, for every partition of $V(G)$ into classes of size $3d-1$, there exists a proper colouring of $G$ with $3d-1$ colours in which each class receives all $3d-1$ colours.

Let I0 be any fixed 3-uniform hypergraph. For a 3-uniform hypergraph H we define vI0 (H) to be the maximum size of a set of pairwise triple-disjoint copies of I0 in H. We say a function ψ from the set of copies of I0 in H to [0, 1] is a fractional I0-packing of H if ΣI ∋ e ψ(I) ≤ 1 for every triple e of H. Then v* I 0 (H) is defined to be the maximum value of Σ I ∈ (H I o) ψ(I) over all fractionalI0-packings ψ of H. We show that vI0* (H) - v I0 (H) = o(|V(H)| 3) for all 3-uniform hypergraphs H. This extends the analogous result for graphs, proved by Haxell and Rodl (2001), and requires a significant amount of new theory about regularity of 3-uniform hypergraphs. In particular, we prove a result that we call the Extension Theorem. This states that if a k-partite 3-uniform hypergraph is regular [in the sense of the hypergraph regularity lemma of Frankl and Rodl (2002)], then almost every triple is in about the same number of copies of Kk(3) (the complete 3-uniform hypergraph with k vertices).

Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].

Let be any fixed graph. For a graph G we define to be the maximum size of a set of pairwise edge-disjoint copies of in G. We say a function from the set of copies of in G to [0, 1] is a fractional -packing of G if for every edge e of G. Then is defined to be the maximum value of over all fractional -packings of G. We show that for all graphs G.

Dobson conjectured that for every t and k a tree with k vertices can always be embedded into a graph of minimum degree max {Δ(T),⌈(k−1)/t⌉} and girth at least 2t+1 . We show that the conjecture holds for all except a finite number of pairs (t,k) .

It is shown that if G is a graph such that the maximum size of a set of pairwise edge-disjoint triangles is v(G), then there is a set C of edges of G of size at most (3 − e)v(G) such that E(T) ∩ C ≠ ∅ for every triangle T of G, where e > 3 23 . This is the first nontrivial bound known for a long-standing conjecture of Tuza.