Article
Computer Science, Information Systems
Hyung-Chan An, Robert Kleinberg
Summary: We present a strengthened version of a lemma by Bondy and Lovasz, which establishes the connectivity of a graph of spanning trees and proves an asymptotically tight bound on the worst-case diameter.
INFORMATION PROCESSING LETTERS
(2022)
Article
Mathematics, Applied
Rogerio G. Alves, Aldo Procacci, Remy Sanchis
Summary: In the context of the probabilistic method in combinatorics, a systematic exploration of the entropy compression method was conducted, clarifying its applicability and providing a general constructive criterion. Through specific examples, the effectiveness of the entropy-compression criterion was demonstrated in comparison with the Lovasz Local Lemma criterion and the improved criterion based on cluster expansion.
ADVANCES IN APPLIED MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
David G. Harris
Summary: The Lovasz Local Lemma (LLL) states that it is possible for a collection of unlikely and relatively independent bad events to not occur simultaneously in a probability space. Moser and Tardos (2010) introduced algorithms that efficiently transform applications of the LLL. A framework by Harvey and Vondrak (2015) extended this to other probability spaces by using resampling oracles, leading to sequential algorithms based on a generalization of the LLL known as the Lopsided Lovasz Local Lemma (LLLL).
ACM TRANSACTIONS ON ALGORITHMS
(2021)
Article
Computer Science, Hardware & Architecture
Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang
Summary: The research introduces a new algorithm based on Markov chains for sampling and approximate counting of CNF formulas that meet certain conditions, achieving faster running times by bypassing connectivity barriers in traditional methods.
JOURNAL OF THE ACM
(2021)
Article
Computer Science, Theory & Methods
William Kuszmaul
Summary: The paper explores the tradeoff curve between the number of wheels on a train car and the amount of track needed for support, proposing methods to build a track that supports the train car but uses minimal track length. Different configurations of the train car are considered, with results showing that an optimal tradeoff curve can be achieved. Techniques from probabilistic combinatorics and randomized algorithms are applied to obtain both upper and lower bounds, demonstrating the versatility of these methods in solving practical problems.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Computer Science, Software Engineering
David G. G. Harris
Summary: The Lovasz local lemma guarantees the existence of configurations that avoid a collection of mostly independent bad events. The MT algorithm provides randomized algorithms for constructions based on the LLL, while deterministic algorithms have been lacking. The authors address three specific shortcomings of prior deterministic algorithms and provide applications to various problems.
RANDOM STRUCTURES & ALGORITHMS
(2023)
Article
Computer Science, Software Engineering
Antonio Girao, Freddie Illingworth, Alex Scott, David R. Wood
Summary: In this paper, it is proved that the vertices of every (r+1)-uniform hypergraph with maximum degree Delta can be colored with a certain number of colors, such that each vertex is in at most d monochromatic edges. This result is a generalization of the classical result of Erdős and Lovász for the d=0 case.
RANDOM STRUCTURES & ALGORITHMS
(2023)
Article
Mathematics
Matija Bucic, Benny Sudakov
Summary: This paper discusses a natural problem raised independently by Erdos-Hajnal and Linial-Rabinovich, and introduces new methods to attack the problem with improved bounds. The first approach is based on bounding Ramsey numbers of certain graphs, improving previous lower bounds. The second approach deals with upper bounds by reducing the original question to a extremal problem.
Article
Mathematics
Francesco Fumagalli, Martino Garonzi, Attila Maroti
Summary: This article studies two functions sigma(G) and omega(G) of the symmetric group G and proves that they both asymptotically tend to 1/2(n/n/2) when n is even. Furthermore, a lower bound of n/5 for omega(G) is provided. The clique number of the graph is also calculated.
DISCRETE MATHEMATICS
(2022)
Proceedings Paper
Computer Science, Theory & Methods
Vishesh Jain, Huy Tuan Pham, Thuy Duong Vuong
Summary: This study introduces a new algorithm for solving constraint satisfaction problems, capable of accurately calculating the number of satisfying assignments and sampling from approximately uniform distributions. The algorithm outperforms previous best known algorithms in several specific cases.
2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021)
(2022)
Article
Automation & Control Systems
Pavel Osinenko, Stefan Streif
Summary: This article investigates the constructive extraction of measurable selectors from set-valued maps, analyzing conditions under which selectors can be extracted and deriving an algorithm for this purpose. The algorithm is applied in a computational study with a three-wheel robot model.
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
(2021)
Article
Mathematics, Applied
Shuwen Xiang, Shunyou Xia, Yanlong Yang
Summary: This paper introduces a generalized labeling on the simplex and presents a slightly different form of the Shapley-Sperner lemma. By applying the KKMS lemma, a direct proof of the Shapley-Sperner lemma is provided, along with a relation between the family of closed subsets C-S in the KKMS lemma and the set of points with label S in the simplex.
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS
(2021)
Article
Computer Science, Artificial Intelligence
Andras Farago
Summary: The Lovasz Local Lemma, a classic result in combinatorics' probabilistic method, reveals that weakly dependent events behave similarly to independent ones. Despite being a purely probabilistic statement, it serves as a valuable and versatile tool in proving deterministic theorems, with various applications and continued research interest.
Article
Operations Research & Management Science
Thanh Le, Cuong Le Van, Ngoc-Sang Pham, Cagri Saglam
Summary: This paper proves the Gale-Nikaido-Debreu lemma using Sperner's lemma and basic elements of topology, which plays an important role in establishing the existence of competitive equilibrium.
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
(2022)
Article
Mathematics
Raphael Beuzart-Plessis
Summary: We present a new proof of the Lie algebra version of the Jacquet-Rallis fundamental lemma for local non-Archimedean fields of characteristic 0. This proof is based on a previous result by Zhang regarding the compatibility of smooth transfer with a (partial) Fourier transform.
DUKE MATHEMATICAL JOURNAL
(2021)
Article
Mathematics
Janos Pach, Gabor Tardos
GRAPHS AND COMBINATORICS
(2015)
Article
Computer Science, Software Engineering
Frederic Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gabor Tardos, David Xiao
RANDOM STRUCTURES & ALGORITHMS
(2016)
Article
Mathematics
Peter L. Erdos, Domotor Palvolgyi, Claude Tardif, Gabor Tardos
Article
Computer Science, Theory & Methods
Janos Pach, Natan Rubin, Gabor Tardos
COMBINATORICS PROBABILITY & COMPUTING
(2016)
Article
Mathematics
Zsolt Langi, Marton Naszodi, Janos Pach, Gabor Tardos, Geza Toth
JOURNAL OF COMBINATORIAL THEORY SERIES A
(2016)
Article
Computer Science, Hardware & Architecture
Heidi Gebauer, Tibor Szabo, Gabor Tardos
JOURNAL OF THE ACM
(2016)
Article
Mathematics
A. Kupavskii, J. Pach, G. Tardos
ACTA MATHEMATICA HUNGARICA
(2018)
Article
Mathematics
Janos Pach, Natan Rubin, Gabor Tardos
ADVANCES IN MATHEMATICS
(2018)
Article
Mathematics
Andrey Kupayskii, Janos Pach, Gabor Tardos
EUROPEAN JOURNAL OF COMBINATORICS
(2018)
Article
Mathematics
Chaya Keller, Shakhar Smorodinsky, Gabor Tardos
ISRAEL JOURNAL OF MATHEMATICS
(2018)
Article
Mathematics
Laszlo Csirmaz, Peter Ligeti, Gabor Tardos
GRAPHS AND COMBINATORICS
(2015)
Article
Mathematics
Gabor Simonyi, Gabor Tardos, Ambrus Zsban
JOURNAL OF GRAPH THEORY
(2015)
Article
Mathematics
Daniel Korandi, Gabor Tardos, Istvan Tomon, Craig Weidert
JOURNAL OF COMBINATORIAL THEORY SERIES A
(2019)
Article
Mathematics, Applied
Andrey Kupavskii, Janos Pach, Gabor Tardos
Proceedings Paper
Computer Science, Theory & Methods
Chaya Keller, Shankhar Smorodibsky, Gabor Tardos
PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS
(2017)