|
Alon–Yuster Conjecture
The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997, is an important result in extremal graph theory, particularly within the context of the regularity method. It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like complete bipartite graphs in the context of embedding spanning graphs of bounded degree. Definitions and Statement To formally state the blow-up lemma, we first need to define the notion of a super-regular pair. Super-regular pairs A pair (A,B) of subsets of the vertex set is called (\varepsilon, \delta)-super-regular if for every X \subset A and Y \subset B satisfying : , X, > \varepsilon , A, and , Y, > \varepsilon , B, we have : e(X,Y) > \delta , X, , Y, and furthermore, : \deg(a) > \delta , B, for all a \in A and \deg(b) > \delta , A, for all b \in B . Here e(X, Y) denotes the number of pairs (x,y) with x \in X and y \in Y such that \ is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
János Komlós (mathematician)
János Komlós (born 23 May 1942, in Budapest) is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He has been a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy of Sciences. Between 1984–1988 he worked at the University of California, San Diego. Notable results * Komlós' theorem: He proved that every L1-bounded sequence of real functions contains a subsequence such that the arithmetic means of all its subsequences converge pointwise almost everywhere. In probabilistic terminology, the theorem is as follows. Let ξ1,ξ2,... be a sequence of random variables such that ''E'' �1''E'' �2... is bounded. Then there exist a subsequence ξ'1, ξ'2,... and a random variable β such that for each further subsequence η1,η2,... of ξ'0, ξ'1,... we have (η1+...+ηn)/n → β a.s. * With Miklós Ajtai ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamiltonian Cycle
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle (graph theory), cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details. Hamiltonian paths and cycles are named after William Rowan Hamilton, who invented the icosian game, now also known as ''Hamilton's puzzle'', which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the icosian calculus, an algebraic structur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Random Graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of ''typical'' graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, ''random graph'' refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a ''random graph''. Models A random graph is obtained by starting with a set of ''n'' isolated vertices and adding successive edges between them at random. The a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sparse Graph
In mathematics, a dense graph is a Graph (discrete mathematics), graph in which the number of edges is close to the maximal number of edges (where every pair of Vertex (graph theory), vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem. The graph density of simple graphs is defined to be the ratio of the number of edges with respect to the maximum possible edges. For undirected simple graphs, the graph density is: :D = \frac = \frac For Directed graph, directed, simple graphs, the maximum possible edges is twice that of undirected graphs (as there are two directions to an edge) so the density is: :D = \frac = \frac where is the number of edges and is the number of vertices in the graph. The maximum number of e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Julia Böttcher
Julia Böttcher is a German discrete mathematician and a professor of mathematics at the London School of Economics. Her research involves graph theory, including graph and hypergraph packing problems, random graphs and random subgraphs, and the relations between graph parameters including graph bandwidth, degree, and chromatic number. Education and career After secondary school in Erfurt, Böttcher studied computer science at the Humboldt University of Berlin, with an exchange year at the University of Toronto. She earned a diploma in 2005. She completed a Ph.D. in mathematics at the Technical University of Munich in 2009, with the dissertation ''Embedding Large Graphs – The Bollobás-Komlós Conjecture and Beyond'' supervised by Anusch Taraz. After postdoctoral research at Technical University of Munich and at the University of São Paulo in Brazil, Böttcher became a lecturer at the London School of Economics in 2012. She was named as an associate professor in 2016 and p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rainbow Coloring
In graph theory, a path in an edge-colored graph is said to be rainbow if no color repeats on it. A graph is said to be rainbow-connected (or rainbow colored) if there is a rainbow path between each pair of its vertices. If there is a rainbow shortest path between each pair of vertices, the graph is said to be strongly rainbow-connected (or strongly rainbow colored). Definitions and bounds The rainbow connection number of a graph G is the minimum number of colors needed to rainbow-connect G, and is denoted by \text(G). Similarly, the strong rainbow connection number of a graph G is the minimum number of colors needed to strongly rainbow-connect G, and is denoted by \text(G). Clearly, each strong rainbow coloring is also a rainbow coloring, while the converse is not true in general. It is easy to observe that to rainbow-connect any connected graph G, we need at least \text(G) colors, where \text(G) is the diameter of G (i.e. the length of the longest shortest path). On the ot ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Peter Keevash
Peter Keevash (born 30 November 1978) is a British mathematician, working in combinatorics. He is a professor of mathematics at the University of Oxford and a Fellow of Mansfield College. Early years Keevash was born in Brighton, England, but mostly grew up in Leeds. He competed in the International Mathematical Olympiad in 1995. He entered Trinity College, University of Cambridge, in 1995 and completed his B.A. in mathematics in 1998. He earned his doctorate from Princeton University with Benny Sudakov as advisor. He took a postdoctoral position at the California Institute of Technology before moving to Queen Mary, University of London as a lecturer, and subsequently professor, before his move to Oxford in September 2013. Mathematics Keevash has published many results in combinatorics, particularly in extremal graph and hypergraph theory and Ramsey Theory. In joint work with Tom Bohman he established the best-known lower bound for the off-diagonal Ramsey Number R(3,k) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Factorization
In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''- regular subgraph, and a ''k''-factorization partitions the edges of the graph into disjoint ''k''-factors. A graph ''G'' is said to be ''k''-factorable if it admits a ''k''-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a ''k''-regular graph is a proper edge coloring with ''k'' colors. A 2-factor is a collection of disjoint cycles that spans all vertices of the graph. 1-factorization If a graph is 1-factorable then it has to be a regular graph. However, not all regular graphs are 1-factorable. A ''k''-regular graph is 1-factorable if it has chromatic index ''k''; examples of such graphs include: * Any regular bipartite graph. Hall's marriage theorem can be used to show that a ''k''-regular bipartite graph contains a perfect matching. One can then remove the perfec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Equitable Coloring
In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that *No two adjacent vertices have the same color, and *The numbers of vertices in any two color classes differ by at most one. That is, the partition of vertices among the different colors is as uniform as possible. For instance, giving each vertex a distinct color would be equitable, but would typically use many more colors than are necessary in an optimal equitable coloring. An equivalent way of defining an equitable coloring is that it is an embedding of the given graph as a subgraph of a Turán graph with the same set of vertices. There are two kinds of chromatic number associated with equitable coloring.. The equitable chromatic number of a graph ''G'' is the smallest number ''k'' such that ''G'' has an equitable coloring with ''k'' colors. But ''G'' might not have equitable colorings for some larger numbers of colors; the equitable ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Raphael Yuster
Raphael "Raphy" Yuster () is an Israeli mathematician specializing in combinatorics and graph theory. He is a professor of mathematics at the University of Haifa. He is a recipient of the Nerode Prize for his work on color-coding, and is also known for the Alon–Yuster conjecture relating the chromatic numbers of graphs to the number of disjoint copies of a smaller graph that can be found in a larger one, later proven by János Komlós, Gábor N. Sárközy, and Endre Szemerédi. Education and career Yuster was a student at Tel Aviv University, where he received a bachelor's degree in 1989, a master's degree in 1991, and a Ph.D. in 1995. His doctoral dissertation, ''Non Constructive Graph Theoretic Proofs and Their Algorithmic Aspects'', was supervised by Noga Alon. He has been a faculty member at the University of Haifa since 2004. Recognition With Noga Alon and Uri Zwick, Yuster was a recipient of the 2019 Nerode Prize, given for their work on color coding, an application ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Noga Alon
Noga Alon (; born 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers. Education and career Alon was born in 1956 in Haifa, where he graduated from the Hebrew Reali School in 1974. He graduated summa cum laude from the Technion – Israel Institute of Technology in 1979, earned a master's degree in mathematics in 1980 from Tel Aviv University, and received his Ph.D. in Mathematics at the Hebrew University of Jerusalem in 1983 with the dissertation ''Extremal Problems in Combinatorics'' supervised by Micha Perles. After postdoctoral research at the Massachusetts Institute of Technology he returned to Tel Aviv University as a senior lecturer in 1985, obtained a permanent position as an associate professor there in 1986, and was promoted to full professor in 1988. He was head of the School of Mathematical Science from 1999 to 2001, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Annals Of Combinatorics
''Annals of Combinatorics'' is a quarterly peer-reviewed scientific journal covering research in combinatorics. It was established in 1997 by William Chen and is published by Birkhäuser. The journal publishes articles in combinatorics and related areas with a focus on algebraic combinatorics, analytic combinatorics, graph theory, and matroid theory. Until December 2019, the journal was edited by George Andrews, William Chen, and Peter Paule. The current editors-in-chief are Frédérique Bassino, Kolja Knauer, and Matjaž Konvalinka. Abstracting and indexing The journal is abstracted and indexed in *MathSciNet, *Science Citation Index Expanded, *Scopus, and *ZbMATH Open. According to the ''Journal Citation Reports'', the journal has a 2022 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a type of journal ranking. Journals with higher impact factor values are considered more prestigious or important within their field. The Im ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
