Search

Your search keyword '"Pach J"' showing total 514 results
Start Over Author "Pach J"
514 results on '"Pach J"'

1. Nearly equal distances in the plane, II

Author

Erdős, P., Makai, Jr., E., and Pach, J.

Subjects
Mathematics - Combinatorics, Mathematics - Metric Geometry, 52C10
Abstract

Let $\{p_1, \ldots , p_n \} \subset {\Bbb{R}}^2$ be a separated point set, i.e., any two points have a distance at least $1$. Let $k \ge 1$ be an integer, and $1 \le t_1 < \ldots < t_k$ be real numbers. Let $\delta > 0$. Suppose for all $1 \le \ell (1) \le \ell (2) < \ell (3) \le k$ that $|t_{\ell (3)} / (t_{\ell (1)} + t_{\ell (2)}) - 1| \ge \delta $. Then for $n \ge n_{k, \delta }$, the number of pairs $\{ p_i,p_j\} $, for which $d(p_i,p_j) \in [t_1, t_1 + 1] \cup \ldots \cup [t_k, t_k + 1] $, is at most $n^2/4 + C_{k,\delta }n$. This is sharp, up to the value of the constant $C_{k,\delta } > 0$., Comment: 9 pages

Published
2021

2. Two nearly equal distances in $R^d$

Author

Erdős, P., Makai, Jr., E., and Pach, J.

Subjects
Mathematics - Metric Geometry, 52C10
Abstract

A set $\cal P$ of $n$ points in $R^d$ is separated if all distances of distinct points are at least~$1$. Then we may ask how many of these distances, with multiplicity, lie in an interval $[t, t + 1]$. The authors and J. Spencer proved that the maximum is $(n^2/2)(1 - 1/d) + O(1)$. The authors showed that for $d = 2$ and $\cal P$ separated, the maximal number of distances, with multiplicity, in the union of $k$ unit intervals is $(n^2/2)$ $(1 - 1/(k + 1) + o(1))$. (In these papers the unit intervals could be replaced by intervals of length $\text{const}_d\cdot n^{1/d}$.) In this paper we show that for $k = 2$, and for any $n$, this maximal number is $(n^2/2)(1 - 1/m_{d - 1} + o(1))$, where $m_{d - 1}$ is the maximal size of a two-distance set in $R^{d - 1}$. (The value of $m_{d - 1}$ is known for $d - 1 \leq 8$, and for each $d$ it lies in $\left[\left({d\atop 2}\right), \left({d + 1\atop 2}\right)\right]$. For $d \neq 4,5$ we can replace unit intervals by intervals of length $\text{const}_d \cdot n^{1/d}$, and the maximum is the respective Tur\'an number, for $n \geq n(d)$.) We also investigate a variant of this question, namely with $k$ intervals of the form $[t, t(1 + \varepsilon)]$, for $\varepsilon < \varepsilon (d, k)$, and for $n > n(d, k)$. Here the maximal number of distances, with multiplicity, in the union of $k$ such intervals is the Tur\'an number $T(n, (d + 1)^k + 1)$. Several of these results were announced earlier by Makai-Pach-Spencer., Comment: 22 pages

Published
2019

4. The Erd\H{o}s-Hajnal conjecture for rainbow triangles

Author

Fox, J., Grinshpun, A., and Pach, J.

Subjects
Mathematics - Combinatorics, 05D10, 05C55, 05C35, 05C15
Abstract

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Omega(n^{1/3}log^2 n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjecture of Hajnal which is a case of the multicolor generalization of the well-known Erd\H{o}s-Hajnal conjecture. We further establish a generalization of this result. For fixed positive integers s and r with s at most r, we determine a constant c_{r,s} such that the following holds. Every r-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Omega(n^{r(r-1)/s(s-1)}(\log n)^{c_{r,s}}) which uses at most s colors, and this bound is tight apart from the implied constant factor. The proof of the lower bound utilizes Gallai's classification of rainbow-triangle free edge-colorings of the complete graph, a new weighted extension of Ramsey's theorem, and a discrepancy inequality in edge-weighted graphs. The proof of the upper bound uses Erd\H{o}s' lower bound on Ramsey numbers by considering lexicographic products of 2-edge-colorings of complete graphs without large monochromatic cliques., Comment: 43 pages

Published
2013

6. Glycemic Control and Urinary Tract Infections in Women with Type 1 Diabetes: Results from the DCCT/EDIC

Author

Nathan, D.M., Zinman, B., Crofford, O., Genuth, S., Brown-Friday, J., Crandall, J., Engel, H., Engel, S., Martinez, H., Phillips, M., Reid, M., Shamoon, H., Sheindlin, J., Gubitosi-Klug, R., Mayer, L., Pendegast, S., Zegarra, H., Miller, D., Singerman, L., Smith-Brewer, S., Novak, M., Quin, J., Genuth, Saul, Palmert, M., Brown, E., McConnell, J., Pugsley, P., Crawford, P., Dahms, W., Brillon, D., Lackaye, M.E., Kiss, S., Chan, R., Orlin, A., Rubin, M., Reppucci, V., Lee, T., Heinemann, M., Chang, S., Levy, B., Jovanovic, L., Richardson, M., Bosco, B., Dwoskin, A., Hanna, R., Barron, S., Campbell, R., Bhan, A., Kruger, D., Jones, J.K., Edwards, P.A., Carey, J.D., Angus, E., Thomas, A., Galprin, A., McLellan, M., Whitehouse, F., Bergenstal, R., Johnson, M., Gunyou, K., Thomas, L., Laechelt, J., Hollander, P., Spencer, M., Kendall, D., Cuddihy, R., Callahan, P., List, S., Gott, J., Rude, N., Olson, B., Franz, M., Castle, G., Birk, R., Nelson, J., Freking, D., Gill, L., Mestrezat, W., Etzwiler, D., Morgan, K., Aiello, L.P., Golden, E., Arrigg, P., Asuquo, V., Beaser, R., Bestourous, L., Cavallerano, J., Cavicchi, R., Ganda, O., Hamdy, O., Kirby, R., Murtha, T., Schlossman, D., Shah, S., Sharuk, G., Silva, P., Silver, P., Stockman, M., Sun, J., Weimann, E., Wolpert, H., Aiello, L.M., Jacobson, A., Rand, L., Rosenzwieg, J., Larkin, M.E., Christofi, M., Folino, K., Godine, J., Lou, P., Stevens, C., Anderson, E., Bode, H., Brink, S., Cornish, C., Cros, D., Delahanty, L., deManbey, A., Haggan, C., Lynch, J., McKitrick, C., Norman, D., Moore, D., Ong, M., Taylor, C., Zimbler, D., Crowell, S., Fritz, S., Hansen, K., Gauthier-Kelly, C., Service, F.J., Ziegler, G., Colligan, R., Schmidt, L., French, B., Woodwick, R., Rizza, R., Schwenk, W.F., Haymond, M., Pach, J., Mortenson, J., Zimmerman, B., Lucas, A., Luttrell, L., Lopes-Virella, M., Caulder, S., Pittman, C., Patel, N., Lee, K., Nutaitis, M., Fernandes, J., Hermayer, K., Kwon, S., Blevins, A., Parker, J., Colwell, J., Lee, D., Soule, J., Lindsey, P., Bracey, M., Farr, A., Elsing, S., Thompson, T., Selby, J., Lyons, T., Yacoub-Wasef, S., Szpiech, M., Wood, D., Mayfield, R., Molitch, M., Adelman, D., Colson, S., Jampol, L., Lyon, A., Gill, M., Strugula, Z., Kaminski, L., Mirza, R., Simjanoski, E., Ryan, D., Johnson, C., Wallia, A., Ajroud-Driss, S., Astelford, P., Leloudes, N., Degillio, A., Schaefer, B., Mudaliar, S., Lorenzi, G., Goldbaum, M., Jones, K., Prince, M., Swenson, M., Grant, I., Reed, R., Lyon, R., Kolterman, O., Giotta, M., Clark, T., Friedenberg, G., Sivitz, W.I., Vittetoe, B., Kramer, J., Bayless, M., Zeitler, R., Schrott, H., Olson, N., Snetselaar, L., Hoffman, R., MacIndoe, J., Weingeist, T., Fountain, C., Mendley, S., Johnsonbaugh, S., Patronas, M., Carney, M., Salemi, P., Liss, R., Hebdon, M., Counts, D., Donner, T., Gordon, J., Hemady, R., Kowarski, A., Ostrowski, D., Steidl, S., Jones, B., Herman, W.H., Martin, C.L., Pop-Busui, R., Greene, D.A., Stevens, M.J., Burkhart, N., Sandford, T., Floyd, J., Bantle, J., Wimmergren, N., Terry, J., Koozekanani, D., Montezuma, S., Rogness, B., Mech, M., Strand, T., Olson, J., McKenzie, L., Kwong, C., Goetz, F., Warhol, R., Hainsworth, D., Goldstein, D., Hitt, S., Giangiacomo, J., Schade, D.S., Canady, J.L., Burge, M.R., Das, A., Avery, R.B., Ketai, L.H., Chapin, J.E., Schluter, M.L., Rich, J., Johannes, C., Hornbeck, D., Schutta, M., Bourne, P.A., Brucker, A., Braunstein, S., Schwartz, S., Maschak-Carey, B.J., Baker, L., Orchard, T., Cimino, L., Songer, T., Doft, B., Olson, S., Becker, D., Rubinstein, D., Bergren, R.L., Fruit, J., Hyre, R., Palmer, C., Silvers, N., Lobes, L., Rath, P. Paczan, Conrad, P.W., Yalamanchi, S., J.Wesche, Bratkowksi, M., Arslanian, S., Rinkoff, J., Warnicki, J., Curtin, D., Steinberg, D., Vagstad, G., Harris, R., Steranchak, L., Arch, J., Kelly, K., Ostrosaka, P., Guiliani, M., Good, M., Williams, T., Olsen, K., Campbell, A., Shipe, C., Conwit, R., Finegold, D., Zaucha, M., Drash, A., Morrison, A., Malone, J.I., Bernal, M.L., Pavan, P.R., Grove, N., Tanaka, E.A., McMillan, D., Vaccaro-Kish, J., Babbione, L., Solc, H., DeClue, T.J., Dagogo-Jack, S., Wigley, C., Ricks, H., Kitabchi, A., Chaum, E., Murphy, M.B., Moser, S., Meyer, D., Iannacone, A., Yoser, S., Bryer-Ash, M., Schussler, S., Lambeth, H., Raskin, P., Strowig, S., Basco, M., Cercone, S., Barnie, A., Devenyi, R., Mandelcorn, M., Brent, M., Rogers, S., Gordon, A., Bakshi, N., Perkins, B., Tuason, L., Perdikaris, F., Ehrlich, R., Daneman, D., Perlman, K., Ferguson, S., Palmer, J., Fahlstrom, R., de Boer, I.H., Kinyoun, J., Van Ottingham, L., Catton, S., Ginsberg, J., McDonald, C., Harth, J., Driscoll, M., Sheidow, T., Mahon, J., Canny, C., Nicolle, D., Colby, P., Dupre, J., Hramiak, I., Rodger, N.W., Jenner, M., Smith, T., Brown, W., May, M., Hagan, J. Lipps, Agarwal, A., Adkins, T., Lorenz, R., Feman, S., Survant, L., White, N.H., Levandoski, L., Grand, G., Thomas, M., Joseph, D., Blinder, K., Shah, G., Burgess, D., Boniuk, I., Santiago, J., Tamborlane, W., Gatcomb, P., Stoessel, K., Ramos, P., Fong, K., Ossorio, P., Ahern, J., Beck, C., Gaston, P., Trail, R., Lachin, J., Cleary, P., Backlund, J., Bebu, I., Braffett, B., Diminick, L., Gao, X., Hsu, W., Klumpp, K., Larsen, M., McGee, P., Sun, W., Villavicencio, S., Anderson, K., Dews, L., Younes, Naji, Rutledge, B., Chan, K., Rosenberg, D., Petty, B., Determan, A., Kenny, D., Williams, C., Cowie, C., Siebert, C., Steffes, M., Arends, V., Bucksa, J., Nowicki, M., Chavers, B., O’Leary, D., Polak, J., Harrington, A., Funk, L., Crow, R., Gloeb, B., Thomas, S., O’Donnell, C., Soliman, E.Z., Zhang, Z.M., Li, Y., Campbell, C., Keasler, L., Hensley, S., Hu, J., Barr, M., Taylor, T., Prineas, R., Feldman, E.L., Albers, J.W., Low, P., Sommer, C., Nickander, K., Speigelberg, T., Pfiefer, M., Schumer, M., Moran, M., Farquhar, J., Ryan, C., Sandstrom, D., Geckle, M., Cupelli, E., Thoma, F., Burzuk, B., Woodfill, T., Danis, R., Blodi, B., Lawrence, D., Wabers, H., Gangaputra, S., Neill, S., Burger, M., Dingledine, J., Gama, V., Sussman, R., Davis, M., Hubbard, L., Budoff, M., Darabian, S., Rezaeian, P., Wong, N., Fox, M., Oudiz, R., Kim, L., Detrano, R., Cruickshanks, K., Dalton, D., Bainbridge, K., Lima, J., Bluemke, D., Turkbey, E., van der Geest, R.J., Liu, C., Malayeri, A., Jain, A., Miao, C., Chahal, H., Jarboe, R., Monnier, V., Sell, D., Strauch, C., Hazen, S., Pratt, A., Tang, W., Brunzell, J., Purnell, J., Natarajan, R., Miao, F., Zhang, L., Chen, Z., Paterson, A., Boright, A., Bull, S., Sun, L., Scherer, S., Lyons, T.J., Jenkins, A., Klein, R., Virella, G., Jaffa, A., Carter, R., Stoner, J., Garvey, W.T., Lackland, D., Brabham, M., McGee, D., Zheng, D., Mayfield, R.K., Maynard, J., Wessells, H., Sarma, A., Dunn, R., Holt, S., Hotaling, J., Kim, C., Clemens, Q., Brown, J., McVary, K., Lenherr, Sara M., Clemens, J. Quentin, Braffett, Barbara H., Cleary, Patricia A., Dunn, Rodney L., Hotaling, James M., Jacobson, Alan M., Kim, Catherine, Herman, William, Brown, Jeanette S., Wessells, Hunter, and Sarma, Aruna V.

Published
2016
Full Text
View/download PDF

8. Weaving patterns of lines and line segments in space

Author

Pach, J., Pollack, R., Welzl, E., Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Asano, Tetsuo, editor, Ibaraki, Toshihide, editor, Imai, Hiroshi, editor, and Nishizeki, Takao, editor

Published
1990
Full Text
View/download PDF

12. Random necklaces require fewer cuts

Author

Alon, Noga, Elboim, Dor, Pach, J��nos, and Tardos, G��bor

Subjects
05D40, 60C05, Probability (math.PR), FOS: Mathematics, Combinatorics (math.CO)
Abstract

It is known that any open necklace with beads of $t$ types in which the number of beads of each type is divisible by $k$, can be partitioned by at most $(k-1)t$ cuts into intervals that can be distributed into $k$ collections, each containing the same number of beads of each type. This is tight for all values of $k$ and $t$. Here, we consider the case of random necklaces, where the number of beads of each type is $km$. Then the minimum number of cuts required for a ``fair'' partition with the above property is a random variable $X(k,t,m)$. We prove that for fixed $k,t,$ and large $m$, this random variable is at least $(k-1)(t+1)/2$ with high probability. For $k=2$, fixed $t$, and large $m$, we determine the asymptotic behavior of the probability that $X(2,t,m)=s$ for all values of $s\le t $. We show that this probability is polynomially small when $s(t+1)/2$, and decays like $��( 1/\log m)$ when $s=(t+1)/2$. We also show that for large $t$, $X(2,t,1)$ is at most $(0.4+o(1))t$ with high probability and that for large $t$ and large ratio $k/\log t$, $X(k,t,1)$ is $o(kt)$ with high probability., 34 pages

Published
2021
Full Text
View/download PDF

13. Disjointness graphs of short polygonal chains

Author

Pach, J��nos, Tardos, G��bor, and T��th, G��za

Subjects
FOS: Mathematics, Combinatorics (math.CO)
Abstract

The {\em disjointness graph} of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph $G$ of any system of segments in the plane is {\em $��$-bounded}, that is, its chromatic number $��(G)$ is upper bounded by a function of its clique number $��(G)$. Here we show that this statement does not remain true for systems of polygonal chains of length $2$. We also construct systems of polygonal chains of length $3$ such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) \emph{$2$-way infinite} polygonal chains of length $3$ is $��$-bounded: for every such graph $G$, we have $��(G)\le(��(G))^3+��(G).$, 14 pages, 4 figures

Published
2021
Full Text
View/download PDF

22. Minimum area isosceles containers

Author

Kiss, Gergely, Pach, J��nos, and Somlai, G��bor

Subjects
51M04, 97G40, 52C15, History and Overview (math.HO), FOS: Mathematics, Metric Geometry (math.MG)
Abstract

We show that every minimum area isosceles triangle containing a given triangle $T$ shares a side and an angle with $T$. This proves a conjecture of Nandakumar motivated by a computational problem. We use our result to deduce that for every triangle $T$, (1) there are at most $3$ minimum area isosceles triangles that contain $T$, and (2) there exists an isosceles triangle containing $T$ whose area is smaller than $\sqrt2$ times the area of $T$. Both bounds are best possible.

Published
2020
Full Text
View/download PDF

23. Erd��s-Hajnal-type results for ordered paths

Author

Pach, J��nos and Tomon, Istv��n

Subjects
FOS: Mathematics, Combinatorics (math.CO)
Abstract

An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer $k$, there exists a constant $c_k>0$ such that any ordered graph $G$ on $n$ vertices with the property that neither $G$ nor its complement contains an induced monotone path of size $k$, has either a clique or an independent set of size at least $n^{c_k}$. This strengthens a result of Bousquet, Lagoutte, and Thomass��, who proved the analogous result for unordered graphs. A key idea of the above paper was to show that any unordered graph on $n$ vertices that does not contain an induced path of size $k$, and whose maximum degree is at most $c(k)n$ for some small $c(k)>0$, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for $k\geq 3$, by a construction of Fox. We provide further examples how this statement fails for ordered graphs avoiding other ordered trees as well., 14 pages, 1 figure

Published
2020
Full Text
View/download PDF

24. Crossings between non-homotopic edges

Author

Pach, J��nos, Tardos, G��bor, and T��th, G��za

Subjects
05C62, 05C10, Computer Science::Discrete Mathematics, FOS: Mathematics, Combinatorics (math.CO), Computer Science::Databases
Abstract

We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on $n>1$ vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with $n$ vertices and $m>4n$ edges is larger than $c\frac{m^2}{n}$ for some constant $c>0$, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as $n$ is fixed and $m$ tends to infinity., Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Published
2020
Full Text
View/download PDF

31. Crossing families

Author

Aronov, B., Erdős, P., Goddard, W., Kleitman, D. J., Klugerman, M., Pach, J., and Schulman, L. J.

Published
1994
Full Text
View/download PDF

35. Discrete And Computational Geometry

Author

Streinu, Ileana, primary, Bezdek, Karoly, additional, Pach, J´anos, additional, Dey, Tamal, additional, Chen, Jianer, additional, Kravets, Dina, additional, Amato, Nancy, additional, and Randolph Franklin, W, additional

Published
1999
Full Text
View/download PDF

39. Colorings with only rainbow arithmetic progressions

Author

Pach, J��nos and Tomon, Istv��n

Subjects
FOS: Mathematics, Combinatorics (math.CO)
Abstract

If we want to color $1,2,\ldots,n$ with the property that all 3-term arithmetic progressions are rainbow (that is, their elements receive 3 distinct colors), then, obviously, we need to use at least $n/2$ colors. Surprisingly, much fewer colors suffice if we are allowed to leave a negligible proportion of integers uncolored. Specifically, we prove that there exist $��,��, 8 pages, 1 figure

Published
2019
Full Text
View/download PDF

43. On the size of $k$-cross-free families

Author

Kupavskii, Andrey, Pach, J��nos, and Tomon, Istv��n

Subjects
graphs, number, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
Abstract

Two subsets $A,B$ of an $n$-element ground set $X$ are said to be \emph{crossing}, if none of the four sets $A\cap B$, $A\setminus B$, $B\setminus A$ and $X\setminus(A\cup B)$ are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family $\mathcal{F}$ of subsets of $X$ does not contain $k$ pairwise crossing elements, then $|\mathcal{F}|=O_{k}(n)$. For $k=2$ and $3$, the conjecture is true, but for larger values of $k$ the best known upper bound, due to Lomonosov, is $|\mathcal{F}|=O_{k}(n\log n)$. In this paper, we improve this bound by showing that $|\mathcal{F}|=O_{k}(n\log^{*} n)$ holds, where $\log^{*}$ denotes the iterated logarithm function., 7 pages

Published
2017

44. Oxidative Stress and Cardiovascular Risk in Type 1 Diabetes Mellitus: Insights From the DCCT/EDIC Study

Author

Tang, W.H. Wilson, primary, McGee, Paula, additional, Lachin, John M., additional, Li, Daniel Y., additional, Hoogwerf, Byron, additional, Hazen, Stanley L., additional, Nathan, D.M., additional, Zinman, B., additional, Crofford, O., additional, Genuth, S., additional, Brown‐Friday, J., additional, Crandall, J., additional, Engel, H., additional, Engel, S., additional, Martinez, H., additional, Phillips, M., additional, Reid, M., additional, Shamoon, H., additional, Sheindlin, J., additional, Gubitosi‐Klug, R., additional, Mayer, L., additional, Pendegast, S., additional, Zegarra, H., additional, Miller, D., additional, Singerman, L., additional, Smith‐Brewer, S., additional, Novak, M., additional, Quin, J., additional, Genuth, Saul, additional, Palmert, M., additional, Brown, E., additional, McConnell, J., additional, Pugsley, P., additional, Crawford, P., additional, Dahms, W., additional, Gregory, N.S., additional, Lackaye, M.E., additional, Kiss, S., additional, Chan, R., additional, Orlin, A., additional, Rubin, M., additional, Brillon, D., additional, Reppucci, V., additional, Lee, T., additional, Heinemann, M., additional, Chang, S., additional, Levy, B., additional, Jovanovic, L., additional, Richardson, M., additional, Bosco, B., additional, Dwoskin, A., additional, Hanna, R., additional, Barron, S., additional, Campbell, R., additional, Bhan, A., additional, Kruger, D., additional, Jones, J.K., additional, Edwards, P.A., additional, Carey, J.D., additional, Angus, E., additional, Thomas, A., additional, Galprin, A., additional, McLellan, M., additional, Whitehouse, F., additional, Bergenstal, R., additional, Johnson, M., additional, Gunyou, K., additional, Thomas, L., additional, Laechelt, J., additional, Hollander, P., additional, Spencer, M., additional, Kendall, D., additional, Cuddihy, R., additional, Callahan, P., additional, List, S., additional, Gott, J., additional, Rude, N., additional, Olson, B., additional, Franz, M., additional, Castle, G., additional, Birk, R., additional, Nelson, J., additional, Freking, D., additional, Gill, L., additional, Mestrezat, W., additional, Etzwiler, D., additional, Morgan, K., additional, Aiello, L.P., additional, Golden, E., additional, Arrigg, P., additional, Asuquo, V., additional, Beaser, R., additional, Bestourous, L., additional, Cavallerano, J., additional, Cavicchi, R., additional, Ganda, O., additional, Hamdy, O., additional, Kirby, R., additional, Murtha, T., additional, Schlossman, D, additional, Shah, S., additional, Sharuk, G., additional, Silva, P., additional, Silver, P., additional, Stockman, M., additional, Sun, J., additional, Weimann, E., additional, Wolpert, H., additional, Aiello, L.M., additional, Jacobson, A., additional, Rand, L., additional, Rosenzwieg, J., additional, Larkin, M.E., additional, Christofi, M., additional, Folino, K., additional, Godine, J., additional, Lou, P., additional, Stevens, C., additional, Anderson, E., additional, Bode, H., additional, Brink, S., additional, Cornish, C., additional, Cros, D., additional, Delahanty, L., additional, eManbey, ., additional, Haggan, C., additional, Lynch, J., additional, McKitrick, C., additional, Norman, D., additional, Moore, D., additional, Ong, M., additional, Taylor, C., additional, Zimbler, D., additional, Crowell, S., additional, Fritz, S., additional, Hansen, K., additional, Gauthier‐Kelly, C., additional, Service, F.J., additional, Ziegler, G., additional, Barkmeier, A., additional, Schmidt, L., additional, French, B., additional, Woodwick, R., additional, Rizza, R., additional, Schwenk, W.F., additional, Haymond, M., additional, Pach, J., additional, Mortenson, J., additional, Zimmerman, B., additional, Lucas, A., additional, Colligan, R., additional, Luttrell, L., additional, Lopes‐Virella, M., additional, Caulder, S., additional, Pittman, C., additional, Patel, N., additional, Lee, K., additional, Nutaitis, M., additional, Fernandes, J., additional, Hermayer, K., additional, Kwon, S., additional, Blevins, A, additional, Parker, J., additional, Colwell, J., additional, Lee, D., additional, Soule, J., additional, Lindsey, P., additional, Bracey, M., additional, Farr, A., additional, Elsing, S., additional, Thompson, T., additional, Selby, J., additional, Lyons, T., additional, Yacoub‐Wasef, S., additional, Szpiech, M., additional, Wood, D., additional, Mayfield, R., additional, Molitch, M., additional, Adelman, D., additional, Colson, S., additional, Jampol, L., additional, Lyon, A., additional, Gill, M., additional, Strugula, Z., additional, Kaminski, L., additional, Mirza, R., additional, Simjanoski, E., additional, Ryan, D., additional, Johnson, C., additional, Wallia, A., additional, Ajroud‐Driss, S., additional, Astelford, P., additional, Leloudes, N., additional, Degillio, A., additional, Schaefer, B., additional, Mudaliar, S., additional, Lorenzi, G, additional, Goldbaum, M., additional, Jones, K., additional, Prince, M., additional, Swenson, M., additional, Grant, I., additional, Reed, R., additional, Lyon, R., additional, Kolterman, O., additional, Giotta, M., additional, Clark, T., additional, Friedenberg, G., additional, Sivitz, W.I., additional, Vittetoe, B., additional, Kramer, J., additional, Bayless, M., additional, Zeitler, R., additional, Schrott, H., additional, Olson, N., additional, Snetselaar, L., additional, Hoffman, R., additional, MacIndoe, J., additional, Weingeist, T., additional, Fountain, C., additional, Miller, R., additional, Johnsonbaugh, S., additional, Patronas, M., additional, Carney, M., additional, Mendley, S., additional, Salemi, P., additional, Liss, R., additional, Hebdon, M., additional, Counts, D., additional, Donner, T., additional, Gordon, J., additional, Hemady, R., additional, Kowarski, A., additional, Ostrowski, D., additional, Steidl, S., additional, Jones, B., additional, Herman, W.H., additional, Martin, C.L., additional, Pop‐Busui, R., additional, Greene, D.A., additional, Stevens, M.J., additional, Burkhart, N., additional, Sandford, T., additional, Floyd, J., additional, Bantle, J., additional, Flaherty, N., additional, Terry, J., additional, Koozekanani, D., additional, Montezuma, S., additional, Wimmergren, N., additional, Rogness, B., additional, Mech, M., additional, Strand, T., additional, Olson, J., additional, McKenzie, L., additional, Kwong, C., additional, Goetz, F., additional, Warhol, R., additional, Hainsworth, D., additional, Goldstein, D., additional, Hitt, S., additional, Giangiacomo, J., additional, Schade, D.S, additional, Canady, J.L., additional, Burge, M.R., additional, Das, A., additional, Avery, R.B., additional, Ketai, L.H., additional, Chapin, J.E., additional, Schluter, M.L., additional, Rich, J., additional, Johannes, C., additional, Hornbeck, D., additional, Schutta, M., additional, Bourne, P.A., additional, Brucker, A., additional, Braunstein, S., additional, Schwartz, S., additional, Maschak‐Carey, B.J., additional, Baker, L., additional, Orchard, T., additional, Cimino, L., additional, Songer, T., additional, Doft, B., additional, Olson, S., additional, Becker, D., additional, Rubinstein, D., additional, Bergren, R.L., additional, Fruit, J., additional, Hyre, R., additional, Palmer, C., additional, Silvers, N., additional, Lobes, L., additional, Rath, P. Paczan, additional, Conrad, P.W., additional, Yalamanchi, S., additional, Wesche, J., additional, Bratkowksi, M., additional, Arslanian, S., additional, Rinkoff, J., additional, Warnicki, J., additional, Curtin, D., additional, Steinberg, D., additional, Vagstad, G., additional, Harris, R., additional, Steranchak, L., additional, Arch, J., additional, Kelly, K., additional, Ostrosaka, P., additional, Guiliani, M., additional, Good, M., additional, Williams, T., additional, Olsen, K., additional, Campbell, A., additional, Shipe, C., additional, Conwit, R., additional, Finegold, D., additional, Zaucha, M., additional, Drash, A., additional, Morrison, A., additional, Malone, J.I., additional, Bernal, M.L., additional, Pavan, P.R., additional, Grove, N., additional, Tanaka, E.A., additional, McMillan, D., additional, Vaccaro‐Kish, J., additional, Babbione, L., additional, Solc, H., additional, DeClue, T.J., additional, Dagogo‐Jack, S., additional, Wigley, C., additional, Ricks, H., additional, Kitabchi, A., additional, Chaum, E., additional, Murphy, M.B., additional, Moser, S., additional, Meyer, D., additional, Iannacone, A., additional, Yoser, S., additional, Bryer‐Ash, M., additional, Schussler, S., additional, Lambeth, H., additional, Raskin, P., additional, Strowig, S., additional, Basco, M., additional, Cercone, S., additional, Barnie, A., additional, Devenyi, R., additional, Mandelcorn, M., additional, Brent, M., additional, Rogers, S., additional, Gordon, A., additional, Bakshi, N., additional, Perkins, B., additional, Tuason, L., additional, Perdikaris, F., additional, Ehrlich, R., additional, Daneman, D., additional, Perlman, K., additional, Ferguson, S, additional, Palmer, J., additional, Fahlstrom, R., additional, de Boer, I.H., additional, Kinyoun, J., additional, Van Ottingham, L., additional, Catton, S., additional, Ginsberg, J., additional, McDonald, C., additional, Harth, J., additional, Driscoll, M., additional, Sheidow, T., additional, Mahon, J., additional, Canny, C., additional, Nicolle, D., additional, Colby, P., additional, Dupre, J., additional, Hramiak, I., additional, Rodger, N.W., additional, Jenner, M., additional, Smith, T., additional, Brown, W., additional, May, M., additional, Lipps Hagan, J., additional, Agarwal, A., additional, Adkins, T., additional, Lorenz, R., additional, Feman, S., additional, Survant, L., additional, White, N.H., additional, Levandoski, L., additional, Grand, G., additional, Thomas, M., additional, Joseph, D., additional, Blinder, K., additional, Shah, G., additional, Burgess, D., additional, Boniuk, I., additional, Santiago, J., additional, Tamborlane, W., additional, Gatcomb, P., additional, Stoessel, K., additional, Ramos, P., additional, Fong, K., additional, Ossorio, P., additional, Ahern, J., additional, Meadema‐Mayer, L., additional, Beck, C., additional, Farrell, K., additional, Quin, J, additional, Gaston, P., additional, Trail, R., additional, Lachin, J., additional, Backlund, J., additional, Bebu, I., additional, Braffett, B., additional, Diminick, L., additional, Gao, X., additional, Hsu, W., additional, Klumpp, K., additional, Pan, H., additional, Trapani, V., additional, Cleary, P., additional, McGee, P., additional, Sun, W., additional, Villavicencio, S., additional, Anderson, K., additional, Dews, L., additional, Younes, Naji, additional, Rutledge, B., additional, Chan, K., additional, Rosenberg, D., additional, Petty, B., additional, Determan, A., additional, Kenny, D., additional, Williams, C., additional, Cowie, C., additional, Siebert, C., additional, Steffes, M., additional, Arends, V., additional, Bucksa, J., additional, Nowicki, M., additional, Chavers, B., additional, O'Leary, D., additional, Polak, J., additional, Harrington, A., additional, Funk, L., additional, Crow, R, additional, Gloeb, B., additional, Thomas, S., additional, O'Donnell, C., additional, Soliman, E.Z., additional, Zhang, Z.M., additional, Li, Y., additional, Campbell, C., additional, Keasler, L., additional, Hensley, S., additional, Hu, J., additional, Barr, M., additional, Taylor, T., additional, Prineas, R., additional, Feldman, E.L., additional, Albers, J.W., additional, Low, P., additional, Sommer, C., additional, Nickander, K., additional, Speigelberg, T., additional, Pfiefer, M., additional, Schumer, M., additional, Moran, M., additional, Farquhar, J., additional, Ryan, C., additional, Sandstrom, D., additional, Geckle, M., additional, Cupelli, E., additional, Thoma, F., additional, Burzuk, B., additional, Woodfill, T., additional, Danis, R., additional, Blodi, B., additional, Lawrence, D., additional, Wabers, H., additional, Gangaputra, S., additional, Neill, S., additional, Burger, M., additional, Dingledine, J., additional, Gama, V., additional, Sussman, R., additional, Davis, M., additional, Hubbard, L., additional, Budoff, M., additional, Darabian, S., additional, Rezaeian, P., additional, Wong, N., additional, Fox, M., additional, Oudiz, R., additional, Kim, L, additional, Detrano, R., additional, Cruickshanks, K., additional, Dalton, D., additional, Bainbridge, K., additional, Lima, J., additional, Bluemke, D., additional, Turkbey, E., additional, der Geest, ., additional, Liu, C., additional, Malayeri, A., additional, Jain, A., additional, Miao, C., additional, Chahal, H., additional, Jarboe, R., additional, Monnier, V., additional, Sell, D., additional, Strauch, C., additional, Hazen, S., additional, Pratt, A., additional, Tang, W., additional, Brunzell, J., additional, Purnell, J., additional, Natarajan, R., additional, Miao, F., additional, Zhang, L., additional, Chen, Z., additional, Paterson, A., additional, Boright, A., additional, Bull, S., additional, Sun, L., additional, Scherer, S., additional, Lyons, T.J., additional, Jenkins, A., additional, Klein, R., additional, Virella, G., additional, Jaffa, A., additional, Carter, R., additional, Stoner, J., additional, Garvey, W.T., additional, Lackland, D., additional, Brabham, M., additional, McGee, D., additional, Zheng, D., additional, Mayfield, R.K., additional, Maynard, J., additional, Wessells, H., additional, Sarma, A, additional, Dunn, R., additional, Holt, S., additional, Hotaling, J., additional, Kim, C., additional, Clemens, Q., additional, Brown, J., additional, and McVary, K., additional

Published
2018
Full Text
View/download PDF

46. Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension

Author

Fox, Jacob, Pach, J��nos, and Suk, Andrew

Subjects
000 Computer science, knowledge, general works, Computer Science, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
Abstract

The Vapnik-Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every $n$-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $e^{(\log n)^{1 - o(1)}}$. The dependence on the VC-dimension is hidden in the $o(1)$ term. This improves the general lower bound, $e^{c\sqrt{\log n}}$, due to Erdos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $e^{\Omega(\log n)}$. Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lov\'asz-Szegedy and Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for graphs with bounded VC-dimension. We extend this lemma to $k$-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be $(1/\varepsilon)^{O(d)}$, improving the original bound of $(1/\varepsilon)^{O(d^2)}$ in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an $O(n^k)$-time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey-Tur\'an numbers for graphs with bounded VC-dimension.

Published
2017
Full Text
View/download PDF

47. Two extensions of the Erd��s-Szekeres problem

Author

Holmsen, Andreas F., Mojarrad, Hossein Nassajian, Pach, J��nos, and Tardos, G��bor

Subjects
FOS: Mathematics, Combinatorics (math.CO)
Abstract

According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\left({n^{2/3}\log n}\right)}$ points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term. A family of $n$ convex bodies in the plane is said to be in convex position if the convex hull of the union of no $n-1$ of its members contains the remaining one. If any three members are in convex position, we say that the family is in general position. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes Toth and by Pach and Toth, respectively. Let $c(n)$ (and $c'(n)$) denote the smallest positive integer $N$ with the property that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$-membered subfamily in convex position. We show that $c(n)\le c'(n)\leq 2^{n+O\left(\sqrt{n\log n}\right)}$.

Published
2017
Full Text
View/download PDF

48. Thrackles: An Improved Upper Bound

Author

Fulek, Radoslav and Pach, J��nos

Subjects
FOS: Mathematics, Combinatorics (math.CO)
Abstract

A {\em thrackle} is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of $n$ vertices has at most $1.3984n$ edges. {\em Quasi-thrackles} are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an {\em odd} number of times. It is also shown that the maximum number of edges of a quasi-thrackle on $n$ vertices is ${3\over 2}(n-1)$, and that this bound is best possible for infinitely many values of $n$., Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

Published
2017
Full Text
View/download PDF

49. 43 Myocardial stunning or necrosis: a new scintigraphic tools for evaluating carbon monoxide cardiotoxicity

Author

Hubalewska-Hola, A, Pach, D, Pach, J, and Szybinski, Z

Subjects
Carbon monoxide -- Health aspects, Heart -- Injuries, Toxicology -- Research, Radioisotope scanning -- Usage, Environmental issues, Health, Pharmaceuticals and cosmetics industries
Abstract

Objectives: Several techniques have been used to detect early manifestations of carbon monoxide cardiotoxicity but an extent of the heart injury is still unclear. The application of myocardial scintigraphy allows [...]

Published
2002

50. Note on k-planar crossing numbers

Author

Pach, J��nos, Sz��kely, L��szl�� A., T��th, Csaba D., and T��th, G��za

Subjects
FOS: Mathematics, Combinatorics (math.CO), 05C10
Abstract

The crossing number $cr(G)$ of a graph $G=(V,E)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k\ge 1$, the $k$-planar crossing number of $G$, $cr_k(G)$, is defined as the minimum of $cr(G_0)+cr(G_1)+\ldots+cr(G_{k-1})$ over all graphs $G_0, G_1,\ldots, G_{k-1}$ with $\cup_{i=0}^{k-1}G_i=G$. It is shown that for every $k\ge 1$, we have $cr_k(G)\le \left(\frac{2}{k^2}-\frac1{k^3}\right)cr(G)$. This bound does not remain true if we replace the constant $\frac{2}{k^2}-\frac1{k^3}$ by any number smaller than $\frac1{k^2}$. Some of the results extend to the rectilinear variants of the $k$-planar crossing number.

Published
2016
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results