Journal: Combinatorica

Abbreviation

Publisher

Springer

Journal Volumes

ISSN

0209-9683
1439-6912

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 38
  • Number of 1-Factorizations of Regular High-Degree Graphs
    Item type: Journal Article
    Ferber, Asaf; Jain, Vishesh; Sudakov, Benny (2020)
    Combinatorica
    A 1-factor in an n-vertex graph G is a collection of n/2 vertex-disjoint edges and a 1-factorization of G is a partition of its edges into edge-disjoint 1-factors. Clearly, a 1-factorization of G cannot exist unless n is even and G is regular (that is, all vertices are of the same degree). The problem of finding 1-factorizations in graphs goes back to a paper of Kirkman in 1847 and has been extensively studied since then. Deciding whether a graph has a 1-factorization is usually a very difficult question. For example, it took more than 60 years and an impressive tour de force of Csaba, Kühn, Lo, Osthus and Treglown to prove an old conjecture of Dirac from the 1950s, which says that every d-regular graph on n vertices contains a 1-factorization, provided that n is even and (Formula presented.). In this paper we address the natural question of estimating F(n, d), the number of 1-factorizations in d-regular graphs on an even number of vertices, provided that (Formula presented.). Improving upon a recent result of Ferber and Jain, which itself improved upon a result of Cameron from the 1970s, we show that (Formula presented.), which is asymptotically best possible. © 2020 János Bolyai Mathematical Society and Springer-Verlag.
  • Finding perfect matchings in bipartite hypergraphs
    Item type: Journal Article
    Annamalai, Chidambaram (2018)
    Combinatorica
  • Hamilton cycles in highly connected and expanding graphs
    Item type: Journal Article
    Hefetz, Dan; Krivelevich, Michael; Szabó, Tibor (2009)
    Combinatorica
  • Extremal Problems For Transversals In Graphs With Bounded Degree
    Item type: Journal Article
    Szabó, Tibor; Tardos, Gábor (2006)
    Combinatorica
  • A Recursive Theta Body for Hypergraphs
    Item type: Journal Article
    Castro-Silva, Davi; de Oliveira Filho, Fernando Mário; Slot, Lucas; et al. (2023)
    Combinatorica
    The theta body of a graph, introduced by Grotschel, Lovasz, and Schrijver (in 1986), is a tractable relaxation of the independent-set polytope derived from the Lovasz theta number. In this paper, we recursively extend the theta body, and hence the theta number, to hypergraphs. We obtain fundamental properties of this extension and relate it to the high-dimensional Hoffman bound of Filmus, Golubev, and Lifshitz. We discuss two applications: triangle-free graphs and Mantel's theorem, and bounds on the density of triangle-avoiding sets in the Hamming cube.
  • Dense Induced Bipartite Subgraphs in Triangle-Free Graphs
    Item type: Journal Article
    Kwan, Matthew; Letzter, Shoham; Sudakov, Benny; et al. (2020)
    Combinatorica
  • Effective Bounds for Induced Size-Ramsey Numbers of Cycles
    Item type: Journal Article
    Bradač, Domagoj; Draganić, Nemanja; Sudakov, Benny (2024)
    Combinatorica
  • K4-free subgraphs of random graphs revisited
    Item type: Journal Article
    Gerke, S.; Schickinger, T.; Prömel, H. J.; et al. (2007)
    Combinatorica
  • Large Independent Sets from Local Considerations
    Item type: Journal Article
    Bucić, Matija; Sudakov, Benny (2023)
    Combinatorica
    The following natural problem was raised independently by Erdos-Hajnal and Linial-Rabinovich in the early '90 s. How large must the independence number alpha (G) of a graph G be whose every m vertices contain an independent set of size r? In this paper, we discuss new methods to attack this problem. The first new approach, based on bounding Ramsey numbers of certain graphs, allows us to improve the previously best lower bounds due to Linial-Rabinovich, Erdos-Hajnal and Alon-Sudakov. As an example, we prove that any n-vertex graph G having an independent set of size 3 among every 7 vertices has alpha (G) >= Omega (n(5)/(12)). This confirms a conjecture of Erdos and Hajnal that alpha (G) should be at least n(1/3)+(epsilon) and brings the exponent halfway to the best possible value of 1/2. Our second approach deals with upper bounds. It relies on a reduction of the original question to the following natural extremal problem. What is the minimum possible value of the 2-density (The 2-density of a graph H is defined as m(2)( H) := max(H)'subset of H,|H' |>= 3 (e(H')-1) / (vertical bar H'vertical bar - 2) of a graph on m vertices having no independent set of size r? This allows us to improve previous upper bounds due to Linial-Rabinovich, Krivelevich and Kostochka-Jancey. As part of our arguments, we link the problem of Erdos-Hajnal and Linial- Rabinovich and our new extremal 2-density problem to a number of other well-studied questions. This leads to many interesting directions for future research.
  • Every non-Euclidean oriented matroid admits a biquadratic final polynomial
    Item type: Journal Article
    Fukuda, Komei; Moriyama, Sonoko; Nakayama, Hiroki; et al. (2009)
    Combinatorica
Publications 1 - 10 of 38