Combinatorics Probability Computing · 2016 · 10 citations · 8 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsEdge ComputingExtremal CombinatoricsGraph AlgorithmsGraph TheoryEdge Density AnalysisEdge-density Problems
We investigate the number of 4-edge paths in graphs with a given number of vertices and edges, proving an asymptotically sharp upper bound on this number. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k -edge stars.
8
Christian Reiher · Annals of Mathematics · 2016 · 107 citations · Full text
Multipodal Structure and Phase Transitions in Large Constrained Graphs
Richard Kenyon, Charles Radin, Kui Ren et al. · Journal of Statistical Physics · 2017 · 44 citations · Full text