Oleg Pikhurko:
Research Papers
Here is the list of my published and submitted papers in the
anti-chronological
order. Full text (pre-publication versions) is
available on-line.
Preprints
- (with S.Glock, J.Kim, L.Lichev, S.Sun)
On
the (k+2,k)-problem of Brown, Erdos and Sos for k=5,6,7,
44pp
- (with X.Liu)
A
note on extremal constructions for the Erdos-Rademacher problem,
13pp
- (with J.Grebik)
Large
deviation principles for graphon sampling, 42pp.
- (with C.T.Conley and J.Grebik)
Local
version of Vizing's theorem for multi-graphs, 9pp
- (with X.Liu)
Finite
Hypergraph Families with Rich Extremal Turan Constructions via Mixing
Patterns, 57 pages
- (with E.Csoka, L.Grabowski, A.Mathe and K.Tyros)
Moser-Tardos
Algorithm with small number of random bits, 31pp.
- (with A.Mathe, J.Noel)
Circle
Squaring with Pieces of Small Boundary and Low Borel Complexity,
49 pages
Accepted
- (with I.Gil Fernandez, J.Kim, H.Liu)
New
lower bounds on kissing numbers and spherical codes in
high dimensions, accepted by American Journal of Mathematics,
20 pages
- (with S.Glock, F.Joos, J.Kim, M.Kuhn, L.Lichev)
On
the (6,4)-problem of Brown, Erdos and Sos, accepted by Proc Amer Math Soc, 11pp
- (with C.T.Conley and J.Grebik) Divisibility of Spheres with Measurable Pieces,
accepted by L'Enseignement Mathematique, 34 pages
2024
2023
- (with H.Liu, M.Sharifzadeh and K.Staden)
Stability
from graph symmetrisation arguments with applications to inducibility,
J London Math Soc 108 (2023) 1121-1162
- (with V.Falgas-Ravry, E.Vaughan, J.Volec)
The codegree threshold of
K_4-, J London Math Soc 107 (2023) 1660-1691
- (with I.Gil Fernandez, J.Hyde, H.Liu and Z.Wu)
Disjoint
isomorphic balanced clique subdivisions,
J Comb Th (B) 161 (2023) 417-436.
- (with X.Liu)
Hypergraph
Turan densities can have arbitrarily large algebraic degree,
J Comb Th (B) 161 (2023) 407-416.
- (with K.Staden)
Stability for the Erdos-Rothschild
problem, Forum of Math, Sigma 11 (2023) Paper e23, 43 pages.
- On
the limit of the positive l-degree Turan problem, Electronic J Comb 30 (2023) Paper 3.25, 15pp
2022
2021
2020
- (with J.Kim, H.Liu and M.Sharifzadeh)
Asymptotic Structure for the
Clique Density Theorem, Discrete Analysis (2020)
Paper
19, 26pp
- (with J.Grebik)
Measurable versions of Vizing's
theorem, Advances in Mathematics, 374 (2020) Paper 107378, 40pp
- (with H.Liu and K.Staden)
The exact minimum
number of triangles in graphs of given order and size,
Forum of Math, Pi 8 (2020) Paper e8, 144pp.
-
Interview with Katherine Staden where she describes this work
- (with M.Kang and T.Makai)
Supersaturation Problem for the Bowtie,
European J Comb 88 (2020) paper 103107, 27pp.
- (with T.Banakh, A.Idzik, I.Protasov and K.Pszczola)
Isometric copies of directed
trees in orientations of graphs,
J Graph Theory 94 (2020) 175-191.
- (with P.Bennett, A.Dudek and B.Lidicky)
Minimizing the number of
5-cycles in graphs with given edge-density,
Combin Prob Comput 29 (2020) 44-67.
2019
2018
2017
2016
2015
- The maximal length of a
gap between r-graph Turan densities, Electr J Combin, 22 (2015) 7pp.
- (with H.Liu and T.Sousa)
Monochromatic
Clique Decompositions of Graphs, J Graph Theory, 80 (2015) 287-298.
- (with V.Falgas-Ravry, E.Marchant and E.Vaughan)
The codegree threshold for 3-graphs with independent neighbourhoods, SIAM J Discr Math,
23 (2015) 1504-1539, certificates.
- (with J.Balogh, P.Hu, B.Lidicky, B.Udvari and J.Volec)
Minimum number of monotone subsequences of length 4 in permutations, Combinat Probab Computing, 24 (2015) 658-679.
- (with J.Hladky, A.Mathe and V.Patel) Poset limits can be totally ordered,
Trans Amer Math Soc, 367 (2015) 4319-4337
2014
- (with C.G.Heise, K.Panagiotou and A.Taraz)
Coloring d-Embeddable k-Uniform Hypergraphs,
Discr Comput Geometry, 52 (2014) 663-679.
- On Possible Turan Densities,
Israel J Math, 201 (2014) 415-454.
- (with K.Litwack and S.Pongnumkul) How to Play Dundee,
Ars Combinatoria, 115 (2014) 63-88.
- (with A.Cooper, J.Schmitt, G.Warrington) Martin Gardner's
Minimum No-3-in-a-line Problem, Amer Math Monthly, 121 (2014)
213-221.
2013
2012
2011
- (with P.Haxell and A.Taraz) Primality
of Trees, Journal of Combinatorics, 2 (2011) 481-500.
- (with O.Verbitsky)
Logical complexity of graphs: a survey,
"Model Theoretic Methods in Finite Combinatorics", M.Grohe
and J.Makowsky (editors), AMS Comtemporary Mathematics Series,
558 (2011) 129-179.
- The Minimum Size of 3-Graphs without a 4-Set
Spanning No or Exactly Three Edges,
Europ J Comb, 23 (2011) 1142-1155.
- (with M.Kang, O.Ravsky, M.Schacht and O.Verbitsky)
Untangling planar graphs from a specified vertex position
- Hard cases, Discr Applied Math, 159 (2011) 789-799.
2010
- (with P.-S. Loh and B.Sudakov)
Maximizing
the Number of q-Colorings, Proc London Math Soc, 101 (2010) 655-696.
- (with T.Bohman, A.Frieze and D.Mubayi) Hypergraphs with
independent neighborhoods, Combinatorica, 30 (2010) 277-293.
- (with T.Bohman and M.Fonoberova)
The Saturation Function of Complete Partite Graphs,
Journal of Combinatorics, 1 (2010) 149-170.
- An Analytic Approach to Stability,
Discrete Math, 310 (2010) 2951-2964.
- (with T.Jiang and Z.Yilma)
Set Systems without
a Strong Simplex, SIAM J Discr Math, 24 (2010) 1038-1045.
- (with T.Bohman, A.Dudek and A.Frieze)
Flips in Graphs,
SIAM J Discr Math, 24 (2010) 1046-1055.
- (with T.Bohman, A.Frieze, and C.Smyth)
Anti-Ramsey Properties of Random Graphs,
J Comb Th (B), 100 (2010) 299-312.
- Finding an Unknown Acyclic
Orientation of a Given
Graph, Comb, Prob & Comput, 19 (2010) 121-131.
2009
2008
- (with A.Beveridge, T.Bohman, A.Frieze) Game Chromatic Index of
Graphs with Given Restrictions on
Degrees, Theoret Computer Sci, 407 (2008) 242-249.
- (with Z.Furedi and D.Mubayi)
Quadruple Systems with Independent Neighborhoods,
J Comb Th (A), 115 (2008) 1552-1560.
- Perfect Matchings and K_4^3-Tilings in
Hypergraphs of
Large Codegree, Graphs & Comb, 24 (2008) 391-404.
- (with D.Mubayi) Constructions of
Non-Principal Families
in Extremal Hypergraph Theory, Discr Math, 308 (2008) 4430-4434.
- (with A.Beveridge) The Connectivity of Extremal
Ramsey Graphs,
Autralasian J Comb, 41 (2008) 57-62.
- An Exact Turan Result for the Generalized Triangle,
Combinatorica, 28 (2008) 187-208.
- (with M.Bednarska) Odd and Even
Cycles in Maker-Breaker
Games,
Europ J Comb, 29 (2008) 742-745.
- (with J.Schmitt)
A Note on Minimum K_{2,3}-Saturated
Graphs, Australasian J Comb, 40 (2008) 211-215.
- (with P.Haxell and A.Thomason) Maximum
Acyclic and Fragmented Sets
in Regular Graphs, J Graph Th, 57 (2008) 149-156.
2007
- Characterization of Product
Anti-Magic
Graphs of Large Order, Graphs & Comb, 23 (2007) 681-689.
- (with J.Spencer and O.Verbitsky) Decomposable
graphs
and
definitions with no quantifier alternation, Europ
J Comb, 28 (2007) 2264-2283.
(Conference version (EuroComb'05), Discr Math
and
Theoretical Comput Sci, AE (2005) 25-30.)
- (with F.Lazebnik and A.Woldar) Maximum
Number of Colorings of
(2k,k^2)-Graphs,
J Graph Th, 56 (2007) 135-148.
- (with T.Sousa) Minimum
H-Decompositions of Graphs,
J Comb Th (B), 97 (2007) 1041-1055.
- (with A.Beveridge, T.Bohman, A.Frieze) Product
Rule Wins a Competitive Game, Proc Amer Math Soc,
135 (2007) 3061-3071.
-
(with T.Schoen)
Integer Sets
Having the Maximum Number of Distinct Differences, Integers,
7 (2007) 9pp.
- (with D.Mubayi) A new generalization of
Mantel's
theorem to k-graphs, J Comb Th (B), 97 (2007)
669-678.
- (with T.Bohman, A.Frieze, T.Luczak, C.Smyth, J.Spencer, and
O.Verbitsky) First Order Definability of Trees and
Sparse Random Graphs, Comb, Prob & Comput, 16,
(2007) 375-400.
- Trees Are Almost Prime,
Discr Math, 307 (2007) 1455-1462.
2006
- (with J.Wojciechowski) Edge-Bandwidth of
Grids and Tori,
Theoret Computer Sci, 369 (2006) 35-43.
- (with Z.Furedi and M.Simonovits) 4-Books of
Three Pages, J Comb
Th (A), 113 (2006) 882-891.
- (with J.Spencer and O.Verbitsky) Succinct
Definitions in the First Order Theory
of Graphs,
Annals Pure Appl Logic, 139 (2006) 74-109.
- (with H.Veith and O.Verbitsky) The First Order
Definability of Graphs:
Upper Bounds for Quantifier Rank, Discr Appl Math, 154
(2006) 2511-2529.
- Dense Edge-Magic Graphs and Thin Additive
Bases,
Discr Math, 306 (2006) 2097-2107.
2005
- (with A.Taraz) Degree Sequences
of F-Free Graphs,
Electronic J Comb, 12 (2005) 12pp.
- (with M.Kang) Maximum K_{r+1}-Free Graphs
Which Are Not
r-Partite,
Mat Studii, 24 (2005) 12-20.
- Minimizing the
Number of Partial Matchings in Bipartite Graphs, Bulletin of ICA,
43 (2005) 13-18.
- (with Z.Furedi and M.Simonovits) On
Triple Systems with Independent
Neighborhoods, Comb, Prob & Comput,
14 (2005) 795-813.
- (with B.Bollobas) Integer Sets with
Prescribed Pairwise
Differences Being Distinct, Europ J Comb, 26 (2005)
607-616.
- (with O.Verbitsky) Descriptive Complexity of
Finite Structures:
Saving the Quantifier Rank, J Symb Logic, 70 (2005)
419-450.
- (with J.H.Kim, J.Spencer and O.Verbitsky) How
Complex are Random Graphs in First Order
Logic?, Random Struc Alg, 26 (2005) 119-145.
- (with C.Greenhill) Bounds on the
Generalised Acyclic
Chromatic Numbers of Bounded Degree Graphs, Graphs
& Comb, 21 (2005) 407-419.
- (with A.Frieze, M.Krivelevich and T.Szabo) The Game of JumbleG,
Comb, Prob & Comp, 14 (2005) 783-793.
- Generating Edge-Labeled Trees,
American Math. Monthly, 112 (2005) 919-921.
- (with M.Bednarska) Biased
Positional Games on Matroids, Europ J Comb, 26
(2005) 271-285.
2004
2003
- (with Z.Furedi and M.Simonovits) The Turan
Density of
the Hypergraph {abc,ade,bde,cde}, Electronic J Comb, 10
(2003) 7pp.
- Breaking Symmetry on Complete
Bipartite
Graphs of Odd Size, Integers, 3 (2003) 9pp.
- (with R.Diestel) On the Cofinality of
Infinite
Partially Ordered Sets: Factoring a Poset into Lean Essential Subsets,
Order, 20 (2003) 53-66.
- Further Asymptotic Size Ramsey Results
Obtained
via
Linear Programming, Discr Math, 273 (2003) 193-202.
- (with A.Kovacec, J.Merikoski and A.Virtanen) Optimizers
for Sub-Sums Subjected to a Sum- and a Schur Convex Constraint with
Applications
to the Estimation of Eigenvalues, Math Inequalities
& Applications, 6 (2003) 745-763.
- Remarks on a Paper by H. Bielak on Size
Ramsey
Numbers, Periodica Math Hung, 47 (2003) 195-200.
- Size Ramsey Numbers of Stars versus
4-Chromatic
Graphs, J Graph Th, 42 (2003) 220-233.
2002
2001
- Lattice Points in Lattice Polytopes, Mathematika,
48 (2001) 15-24.
- Constructing Designs Straightforwardly:
Worst
Arising
Cases, J Comb Designs, 9 (2001) 100-106.
- Size Ramsey Numbers of Stars versus
3-Chromatic Graphs, Combinatorica, 21
(2001) 403-412.
- Uniform Families and Count Matroids, Graphs
& Comb, 17 (2001) 729-740.
- Weakly Saturated Hypergraphs and Exterior
Algebra, Comb,
Prob & Comp, 10 (2001) 435-451.
2000
1999
1997
1994
1992
Book
(Edited with A.Czumaj, A.Geogakopoulos, D.Kral' and V.Lozin)
Surveys in Combinatorics, Cambridge University Press, 2015.
Edited Oberwolfach Reports
PhD thesis
Here I include my PhD thesis "Extremal Hypergraphs" (written under
supervision
of Andrew Thomason), xii+150pp. (Oct'99), in postscript
(1.2Mb), pdf (1Mb) or in gzip+dvi (250Kb) format.
Various manuscripts
- (with L.Grabowski and A.Mathe) Measurable equidecompositions via combinatorics and group theory, 6pp.
- Borsuk's Conjecture Fails in Dimensions 321 and 322, arXiv:math.CO/0202112,
3pp.
- (with B.Sudakov and D.Mubayi)
Hypergraph Turan Problem: Some
Open Questions, 17pp.
- (with J.Nesetril and B.Szegedy)
Graph Limits: Some Open Questions,
5pp.