搜索结果: 1-11 共查到“组合数学 1/3-2/3 Conjecture”相关记录11条 . 查询时间(0.031 秒)
Jinyoung Park and Huy Tuan Pham Prove the Kahn-Kalai Conjecture（图）
Kahn-Kalai Conjecture probabilistic combinatorics phase transition the expectation threshold conjecture
font style='font-size:12px;'>
2022/4/25
Past Member (2020–21) Jinyoung Park, a Szegö Assistant Professor at Stanford University, and Huy Tuan Pham, a Stanford Ph.D. student, proved the Kahn-Kalai Conjecture, a central problem in probab...
Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments
Hamilton decompositions regular expanders Kelly's conjecture large tournaments
font style='font-size:12px;'>
2012/2/29
A long-standing conjecture of Kelly states that every regular tournament on n vertices can be decomposed into (n-1)/2 edge-disjoint Hamilton cycles. We prove this conjecture for large n. In fact, we p...
The 1/3-2/3 conjecture for $N$-free ordered sets
Ordered set Linear extension N-free Balanced pair 1/3-2/3 Conjecture
font style='font-size:12px;'>
2011/9/22
Abstract: A balanced pair in a finite ordered set $P=(V,\leq)$ is a pair $(x,y)$ of elements of $V$ such that the proportion of linear extensions of $P$ that put $x$ before $y$ is in the real interval...
Counterexamples to a Monotonicity Conjecture for the Threshold Pebbling Number
combinatorics probability theory graph theory graph pebbling pebbling number pebbling threshold
font style='font-size:12px;'>
2011/9/20
Abstract: Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move. This p...
On a conjecture of Erdos and Simonovits: Even Cycles
conjecture of Erdos and Simonovits Even Cycles Combinatorics
font style='font-size:12px;'>
2011/9/19
Abstract: Let $\mc{F}$ be a family of graphs. A graph is {\em $\mc{F}$-free} if it contains no copy of a graph in $\mc{F}$ as a subgraph. A cornerstone of extremal graph theory is the study of the {\e...
Scott's induced subdivision conjecture for maximal triangle-free graphs
Scott's subdivision conjecture maximal triangle-free graphs Combinatorics
font style='font-size:12px;'>
2011/9/14
Abstract: Scott conjectured that the class of graphs with no induced subdivision of a given graph is $\chi$-bounded. We verify his conjecture for maximal triangle-free graphs.
On the Caccetta-Haggkvist conjecture with forbidden subgraphs
the Caccetta-Haggkvist conjecture forbidden subgraphs Combinatorics
font style='font-size:12px;'>
2011/9/2
Abstract: The Caccetta-Haggkvist conjecture made in 1978 asserts that every orgraph on n vertices without oriented cycles of length <= l must contain a vertex of outdegree at most (n-1)/l. It has a ra...
On a Conjecture of Butler and Graham
Conjecture of Butler and Graham Combinatorics Discrete Mathematics
font style='font-size:12px;'>
2011/9/1
Abstract: In this paper we prove a conjecture of Bulter and Graham \cite{Butler11} on the existence of a certain way of marking the lines in $[k]^n$ for any prime $k$. The conjecture states that there...
On the logarithimic calculus and Sidorenko's conjecture
logarithimic calculus Sidorenko's conjecture Combinatorics
font style='font-size:12px;'>
2011/8/26
Abstract: We study a type of calculus for proving inequalities between subgraph densities which is based on Jensen's inequality for the logarithmic function. As a demonstration of the method we verify...
Cartan matrices and Brauer's k(B)-conjecture
Cartan matrices Brauer’s k(B)-conjecture decomposition matrices quadratic forms
font style='font-size:12px;'>
2011/2/24
It is well known that the Cartan matrix of a block of a finite group cannot be arranged as a direct sum of smaller matrices. In this paper we address the question if this remains true for equivalent m...
Logarithms of iteration matrices, and proof of a conjecture by Shadrin and Zvonkine
Logarithms of iteration matrices proof of a conjecture by Shadrin Zvonkine
font style='font-size:12px;'>
2010/12/14
A proof for a conjecture by Shadrin and Zvonkine, relating the en-tries of a matrix arising in the study of Hurwitz numbers to a certain sequence of rational numbers, is given. The main tools used are...