skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Generalizations and Strengthenings of Ryser's Conjecture
Ryser's conjecture says that for every $$r$$-partite hypergraph $$H$$ with matching number $$\nu(H)$$, the vertex cover number is at most $$(r-1)\nu(H)$$.  This far-reaching generalization of König's theorem is only known to be true for $$r\leq 3$$, or when $$\nu(H)=1$$ and $$r\leq 5$$.  An equivalent formulation of Ryser's conjecture is that in every $$r$$-edge coloring of a graph $$G$$ with independence number $$\alpha(G)$$, there exists at most $$(r-1)\alpha(G)$$ monochromatic connected subgraphs which cover the vertex set of $$G$$.   We make the case that this latter formulation of Ryser's conjecture naturally leads to a variety of stronger conjectures and generalizations to hypergraphs and multipartite graphs.  Regarding these generalizations and strengthenings, we survey the known results, improving upon some, and we introduce a collection of new problems and results.  more » « less
Award ID(s):
1954170
PAR ID:
10335796
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
28
Issue:
4
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, The Electronic Journal of Combinatorics)
    For an $$r$$-uniform hypergraph $$H$$, let $$\nu^{(m)}(H)$$ denote the maximum size of a set $$M$$ of edges in $$H$$ such that every two edges in $$M$$ intersect in less than $$m$$ vertices, and let $$\tau^{(m)}(H)$$ denote the minimum size of a collection $$C$$ of $$m$$-sets of vertices such that every edge in $$H$$ contains an element of $$C$$. The fractional analogues of these parameters are denoted by $$\nu^{*(m)}(H)$$ and $$\tau^{*(m)}(H)$$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$$. In this paper we prove bounds on the ratio between the parameters $$\tau^{(m)}$$ and $$\nu^{(m)}$$, and their fractional analogues. Our main result is that, for every $$r$$-uniform hypergraph~$$H$$,\[ \tau^{*(r-1)}(H)/\nu^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $$r-1$.We also prove that, for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$$, where the Turán number $$\operatorname{ex}_r(n, k)$$ is the maximum number of edges in an $$r$$-uniform hypergraph on $$n$$ vertices that does not contain a copy of the complete $$r$$-uniform hypergraph on $$k$$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$. 
    more » « less
  2. ; ; (, Graphs and Combinatorics)
    The Gyárfás–Sumner conjecture says that for every tree T and every integer t ≥ 1, if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T. This remains open, but we prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is “path-induced”; that is, for some distinguished vertex r, every path of H with one end r is an induced path of G. 
    more » « less
  3. ; ; ; (, Advances in Combinatorics)
    A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 
    more » « less
  4. ; (, The Electronic Journal of Combinatorics)
    Let $$G$$ be a multigraph. A subset $$F$$ of $E(G)$ is an edge cover of $$G$$ if every vertex of $$G$$ is incident to an edge of $$F$$. The cover index, $$\xi(G)$$, is the largest number of edge covers into which the edges of $$G$$ can be partitioned. Clearly $$\xi(G) \le \delta(G)$$, the minimum degree of $$G$$. For $$U\subseteq V(G)$$, denote by $E^+(U)$ the set of edges incident to a vertex of $$U$$. When $|U|$ is odd, to cover all the vertices of $$U$$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $$ \xi(G) \le |E^+(U)|/ ((|U|+1)/2)$$. Let $$\rho_c(G)$$, the co-density of $$G$$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $$U\subseteq V(G)$$, where $$|U| \ge 3$$ and $|U|$ is odd. Then $$\rho_c(G)$$ provides another upper bound on $$\xi(G)$$. Thus $$\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$$. For a lower bound on $$\xi(G)$$, in 1978, Gupta conjectured that $$\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$$. Gupta himself verified the conjecture for simple graphs, and Cao et al. recently verified this conjecture when $$\rho_c(G)$$ is not an integer. In this paper, we confirm the conjecture when the maximum multiplicity of $$G$$ is at most two or $$ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$$. The proof relies on a newly established result on edge colorings. The result holds independent interest and has the potential to significantly contribute towards resolving the conjecture entirely. 
    more » « less
  5. ; ; (, Transactions of the American Mathematical Society)
    Let G G be a finite group admitting a coprime automorphism α \alpha of order e e . Denote by I G ( α ) I_G(\alpha ) the set of commutators g − 1 g α g^{-1}g^\alpha , where g ∈ G g\in G , and by [ G , α ] [G,\alpha ] the subgroup generated by I G ( α ) I_G(\alpha ) . We study the impact of I G ( α ) I_G(\alpha ) on the structure of [ G , α ] [G,\alpha ] . Suppose that each subgroup generated by a subset of I G ( α ) I_G(\alpha ) can be generated by at most r r elements. We show that the rank of [ G , α ] [G,\alpha ] is ( e , r ) (e,r) -bounded. Along the way, we establish several results of independent interest. In particular, we prove that if every element of I G ( α ) I_G(\alpha ) has odd order, then [ G , α ] [G,\alpha ] has odd order too. Further, if every pair of elements from I G ( α ) I_G(\alpha ) generates a soluble, or nilpotent, subgroup, then [ G , α ] [G,\alpha ] is soluble, or respectively nilpotent. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email